Vi presenterar två nya och effektiva algoritmer för att beräkna alla-par kortaste vägar. Algoritmerna arbetar med riktade grafer med verkliga (eventuellt negativa) vikter. De använder sig av riktad vägkonsistens längs en vertex beställning d. Båda algoritmer kör i O n 2 w d tid, där w d är grafbredden induceras av denna vertex beställning. För grafer av konstant trädbredd, ger detta O n 2 tid, vilket är optimalt. På ackorddiagram kör algoritmerna i O (nm) tid. Dessutom presenterar vi en variant som utnyttjar grafseparatorer för att komma fram till en körtid på O nw 2 d + n 2 s d på allmänna grafer, där s d ≤ w d är storleken på den största minimala separator som induceras av vertex beställning d. Vi visar empiriskt att på både konstruerade och realistiska riktmärken, i många fall algoritmer överträffar Floyd-Warshalls liksom Johnsons algoritm, som representerar den nuvarande tekniken med en körtid på O n 3 och O nm + n 2 log n, respektive. Våra algoritmer kan användas för rumsliga och tidsmässiga resonemang, t.ex. för det enkla tidsmässiga problemet, vilket understryker deras relevans för planerings- och schemaläggningsgemenskapen.
Lyckligtvis kan vi beräkna alla-par kortaste vägar i inducerade grafer genom att utnyttja låg trädbredd REF.
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
{'venue': 'Journal Of Artificial Intelligence Research, Volume 43, pages 353-388, 2012', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}