Problém s nejkratší cestou - Shortest path problem

Nejkratší cesta (A, C, E, D, F) mezi vrcholy A a F ve váženém orientovaném grafu

v teorie grafů, problém s nejkratší cestou je problém najít cesta mezi dvěma vrcholy (nebo uzly) v a graf tak, že součet závaží jeho základních hran je minimalizováno.

Problém nalezení nejkratší cesty mezi dvěma křižovatkami na cestovní mapě lze modelovat jako speciální případ problému s nejkratší cestou v grafech, kde vrcholy odpovídají křižovatkám a hrany odpovídají úsekům silnice, každý vážený délkou segment.

Definice

Lze definovat problém s nejkratší cestou grafy zda neorientovaný, režie nebo smíšený Je zde definována pro neorientované grafy; pro směrované grafy definice cesty vyžaduje, aby po sobě jdoucí vrcholy byly spojeny příslušnou směrovanou hranou.

Dva vrcholy sousedí, když oba dopadají na společnou hranu cesta v neorientovaném grafu je a sekvence vrcholů ${ displaystyle P = (v_ {1}, v_ {2}, ldots, v_ {n}) v V krát V krát cdoty krát V}$ takhle ${ displaystyle v_ {i}}$ sousedí s ${ displaystyle v_ {i + 1}}$ pro ${ displaystyle 1 leq i$ .Taková cesta ${ displaystyle P}$ se nazývá cesta délky ${ displaystyle n-1}$ z ${ displaystyle v_ {1}}$ na ${ displaystyle v_ {n}}$ (The ${ displaystyle v_ {i}}$ jsou proměnné; jejich číslování zde souvisí s jejich pozicí v pořadí a nemusí se vztahovat k žádnému kanonickému označování vrcholů.)

Nechat ${ displaystyle e_ {i, j}}$ být hranou incidentu pro oba ${ displaystyle v_ {i}}$ a ${ displaystyle v_ {j}}$ . Vzhledem k tomu, skutečný váhová funkce ${ displaystyle f: E rightarrow mathbb {R}}$ a neusměrněný (jednoduchý) graf ${ displaystyle G}$ , nejkratší cesta z ${ displaystyle v}$ na ${ displaystyle v '}$ je cesta ${ displaystyle P = (v_ {1}, v_ {2}, ldots, v_ {n})}$ (kde ${ displaystyle v_ {1} = v}$ a ${ displaystyle v_ {n} = v '}$ ) to je možné ${ displaystyle n}$ minimalizuje součet ${ displaystyle sum _ {i = 1} ^ {n-1} f (e_ {i, i + 1}).}$ Když má každá hrana v grafu jednotkovou hmotnost nebo ${ displaystyle f: E rightarrow {1 }}$ , to je ekvivalentní hledání cesty s nejmenším počtem hran.

Problém se někdy také nazývá problém s nejkratší cestou jednoho páru, aby se odlišil od následujících variant:

The problém s nejkratší cestou jednoho zdroje, ve kterém musíme najít nejkratší cesty ze zdrojového vrcholu proti na všechny ostatní vrcholy v grafu.
The problém s nejkratší cestou jednoho cíle, ve kterém musíme najít nejkratší cesty ze všech vrcholů v směrovaném grafu k jednomu cílovému vrcholu proti. To lze snížit na problém s nejkratší cestou jednoho zdroje obrácením oblouků v směrovaném grafu.
The problém s nejkratší cestou všech párů, ve kterém musíme najít nejkratší cesty mezi každou dvojicí vrcholů proti, proti' v grafu.

Tyto zobecnění mají podstatně efektivnější algoritmy než zjednodušující přístup ke spuštění algoritmu nejkratší cesty s jedním párem na všech příslušných párech vrcholů.

Algoritmy

Nejdůležitějšími algoritmy pro řešení tohoto problému jsou:

Dijkstrův algoritmus řeší problém nejkratší cesty s jedním zdrojem s nezápornou váhou hrany.
Algoritmus Bellman-Ford řeší problém s jedním zdrojem, pokud okrajové váhy mohou být záporné.
* Vyhledávací algoritmus řeší nejkratší cestu jednoho páru pomocí heuristiky, aby se pokusil zrychlit hledání.
Floyd – Warshallův algoritmus řeší všechny páry nejkratší cesty.
Johnsonův algoritmus řeší všechny páry nejkratších cest a může být rychlejší než Floyd – Warshall řídké grafy.
Viterbiho algoritmus řeší problém nejkratší stochastické dráhy s další pravděpodobnostní váhou na každém uzlu.

Další algoritmy a související hodnocení lze nalézt v Cherkassky, Goldberg & Radzik (1996).

Nejkratší cesty jednoho zdroje

Neorientované grafy

Závaží	Časová složitost	Autor
ℝ₊	Ó(PROTI²)	Dijkstra 1959
ℝ₊	Ó((E + PROTI) logPROTI)	Johnson 1977 (binární hromada )
ℝ₊	Ó(E + PROTI logPROTI)	Fredman & Tarjan 1984 (Fibonacciho hromada )
ℕ	Ó(E)	Thorup 1999 (vyžaduje násobení v konstantním čase)

Nevážené grafy

Algoritmus	Časová složitost	Autor
Šířka první vyhledávání	Ó(E + PROTI)

Směrované acyklické grafy (DAG)

Použitý algoritmus topologické třídění může vyřešit problém s nejkratší cestou s jedním zdrojem v čase $Θ (E + PROTI)$ v libovolně vážených DAG.^[1]

Směrované grafy s nezápornými váhami

Následující tabulka je převzata z Schrijver (2004), s některými opravami a dodatky. Zelené pozadí označuje asymptoticky nejlépe vázané v tabulce; L je maximální délka (nebo hmotnost) mezi všemi hranami, za předpokladu celočíselné hmotnosti hran.

Závaží	Algoritmus	Časová složitost	Autor
ℝ		Ó(PROTI²EL)	Ford 1956
ℝ	Algoritmus Bellman-Ford	Ó(VE)	Shimbel 1955, Bellman 1958, Moore 1959
ℝ		Ó(PROTI² logPROTI)	Dantzig 1960
ℝ	Dijkstrův algoritmus se seznamem	Ó(PROTI²)	Leyzorek a kol. 1957, Dijkstra 1959, Minty (viz Pollack & Wiebenson 1960 ), Whiting & Hillier 1960
ℝ	Dijkstrův algoritmus s binární hromada	Ó((E + PROTI) logPROTI)	Johnson 1977
ℝ	Dijkstrův algoritmus s Fibonacciho hromada	Ó(E + PROTI logPROTI)	Fredman & Tarjan 1984, Fredman & Tarjan 1987
ℕ	Dialův algoritmus^[2] (Dijkstrův algoritmus používat fronta na kbelík s L kbelíky)	Ó(E + LV)	Vytočit 1969
		Ó(E log logL)	Johnson 1981, Karlsson & Poblete 1983
	Gabowův algoritmus	Ó(E log_E/PROTI L)	Gabow 1983, Gabow 1985
		Ó(E + PROTI √log L)	Ahuja et al. 1990
	Thorup	Ó(E + PROTI log logPROTI)	Thorup 2004

Směrované grafy s libovolnými váhami bez negativních cyklů

Závaží	Algoritmus	Časová složitost	Autor
ℝ		Ó(PROTI²EL)	Ford 1956
ℝ	Algoritmus Bellman-Ford	Ó(VE)	Shimbel 1955, Bellman 1958, Moore 1959
ℝ	Johnson-Dijkstra s binární hromada	Ó(PROTI (E + logPROTI))	Johnson 1977
ℝ	Johnson-Dijkstra s Fibonacciho hromada	Ó(PROTI (E + logPROTI))	Fredman & Tarjan 1984, Fredman & Tarjan 1987, upraveno po Johnson 1977
ℕ	Johnsonova technika aplikován na Dialův algoritmus^[2]	Ó(PROTI (E + L))	Vytočit 1969, upraveno po Johnson 1977

Rovinné směrované grafy s libovolnými váhami

Nejkratší cesty všech párů

Problém s nejkratší cestou všech párů najde nejkratší cesty mezi každou dvojicí vrcholů $proti$ , $proti'$ v grafu. Problém nejkratších cest všech párů pro nevážené směrované grafy představil Shimbel (1953), kteří pozorovali, že by to mohlo být vyřešeno lineárním počtem násobení matic, které by trvalo celkem $Ó (PROTI 4)$ .

Neusměrněný graf

Závaží	Časová složitost	Algoritmus
ℝ₊	$Ó (PROTI 3)$	Floyd – Warshallův algoritmus
${ displaystyle {1, infty }}$	${ displaystyle O (V ^ { omega} log V)}$	Seidelův algoritmus (očekávaná doba provozu)
ℕ	${ displaystyle O (V ^ {3} / 2 ^ { Omega ( log n) ^ {1/2}})}$	Williams 2014
ℝ₊	$Ó (EV log α (E, PROTI))$	Pettie & Ramachandran 2002
ℕ	$Ó (EV)$	Thorup 1999 aplikován na každý vrchol (vyžaduje násobení v konstantním čase).

Směrovaný graf

Závaží	Časová složitost	Algoritmus
ℝ (žádné negativní cykly)	$Ó (PROTI 3)$	Floyd – Warshallův algoritmus
ℕ	${ displaystyle O (V ^ {3} / 2 ^ { Omega ( log n) ^ {1/2}})}$	Williams 2014
ℝ (žádné negativní cykly)	$Ó (EV + PROTI 2 log PROTI)$	Johnson – Dijkstra
ℝ (žádné negativní cykly)	$Ó (EV + PROTI 2 log log PROTI)$	Pettie 2004
ℕ	$Ó (EV + PROTI 2 log log PROTI)$	Hagerup 2000

Aplikace

Algoritmy nejkratší cesty se používají k automatickému vyhledání směrů mezi fyzickými místy, jako jsou například směry jízdy mapování webu webové stránky jako MapQuest nebo Google mapy. Pro tuto aplikaci jsou k dispozici rychlé specializované algoritmy.^[3]

Pokud jeden představuje nedeterministické abstraktní stroj jako graf, kde vrcholy popisují stavy a hrany popisují možné přechody, lze použít algoritmy nejkratší cesty k nalezení optimální posloupnosti voleb k dosažení určitého stavu cíle nebo k stanovení nižších mezí času potřebného k dosažení daného stavu. Například pokud vrcholy představují stavy hádanky jako a Rubikova kostka a každá směrovaná hrana odpovídá jednomu tahu nebo otočení, lze použít algoritmy nejkratší cesty k nalezení řešení, které využívá minimální možný počet tahů.

V síťování nebo telekomunikace myšlení, tento problém s nejkratší cestou se někdy nazývá problém cesty s minimálním zpožděním a obvykle se spojuje s a problém s nejširší cestou. Algoritmus může například hledat nejkratší (minimální zpoždění) nejširší cestu nebo nejširší nejkratší (minimální zpoždění) cestu.

Bezstarostnější aplikací jsou hry „šest stupňů oddělení „kteří se snaží najít nejkratší cestu v grafech, jako jsou filmové hvězdy, které se objevují ve stejném filmu.

Další aplikace, často studované v operační výzkum, zahrnovat uspořádání závodu a zařízení, robotika, přeprava, a VLSI design.^[4]

Silniční sítě

Silniční síť lze považovat za graf s kladnými váhami. Uzly představují silniční křižovatky a každá hrana grafu je spojena s úsekem silnice mezi dvěma křižovatkami. Váha hrany může odpovídat délce příslušného segmentu silnice, času potřebnému k projetí segmentu nebo nákladům na přejetí segmentu. Pomocí směrovaných hran je také možné modelovat jednosměrné ulice. Takové grafy jsou zvláštní v tom smyslu, že některé hrany jsou pro cestování na dlouhé vzdálenosti důležitější než jiné (např. Dálnice). Tato vlastnost byla formována pomocí pojmu dálniční dimenze.^[5] Existuje velké množství algoritmů, které tuto vlastnost využívají, a proto jsou schopné vypočítat nejkratší cestu mnohem rychleji, než by to bylo možné v obecných grafech.

Všechny tyto algoritmy fungují ve dvou fázích. V první fázi je graf předzpracován bez znalosti zdrojového nebo cílového uzlu. Druhá fáze je fáze dotazu. V této fázi jsou známé zdrojový a cílový uzel. Myšlenka je, že silniční síť je statická, takže fázi předzpracování lze provést jednou a použít ji pro velké množství dotazů na stejné silniční síti.

Algoritmus s nejrychleji známou dobou dotazu se nazývá označení náboje a je schopen vypočítat nejkratší cestu v silničních sítích Evropy nebo USA za zlomek mikrosekundy.^[6] Další techniky, které byly použity, jsou:

ALT (Hledání, orientační body a nerovnost trojúhelníku )
Vlajky oblouku
Hierarchie kontrakcí
Směrování tranzitního uzlu
Prořezávání na základě dosahu
Značení
Štítky nábojů

Související problémy

Pro problémy s nejkratší cestou v výpočetní geometrie viz Euklidovská nejkratší cesta.

The problém obchodního cestujícího je problém najít nejkratší cestu, která prochází každým vrcholem přesně jednou a vrátí se na začátek. Na rozdíl od problému s nejkratší cestou, který lze vyřešit v polynomiálním čase v grafech bez negativních cyklů, je problém obchodního cestujícího NP-kompletní a proto se věří, že není efektivně řešitelný pro velké soubory dat (viz P = NP problém ). Problém najít nejdelší cestu v grafu je také NP-kompletní.

The Kanadský cestovatelský problém a stochastickým problémem s nejkratší cestou jsou zevšeobecňování, kde buď graf není zcela znám pohybujícímu se subjektu, mění se v čase, nebo kde jsou akce (procházení) pravděpodobnostní.

Nejkratší vícenásobně odpojená cesta ^[7] je reprezentace sítě primitivních cest v rámci Reptační teorie.

The problém s nejširší cestou hledá cestu tak, aby minimální štítek kterékoli hrany byl co největší.

Strategické nejkratší cesty

Někdy mají hrany v grafu osobnosti: každá hrana má svůj vlastní sobecký zájem. Příkladem je komunikační síť, ve které je každá hrana počítač, který možná patří jiné osobě. Různé počítače mají různé přenosové rychlosti, takže každá hrana v síti má číselnou váhu rovnou počtu milisekund potřebných k přenosu zprávy. Naším cílem je odeslat zprávu mezi dvěma body v síti v co nejkratším čase. Pokud známe dobu přenosu každého počítače (váhu každé hrany), můžeme použít standardní algoritmus nejkratších cest. Pokud neznáme časy přenosu, musíme požádat každý počítač, aby nám sdělil svůj čas přenosu. Ale počítače mohou být sobecké: počítač nám může říct, že jeho doba přenosu je velmi dlouhá, takže ho nebudeme obtěžovat svými zprávami. Možným řešením tohoto problému je použití varianta mechanismu VCG, což dává počítačům motivaci odhalit jejich skutečné váhy.

Formulace lineárního programování

Existuje přírodní lineární programování formulace pro problém s nejkratší cestou, uvedená níže. Je to velmi jednoduché ve srovnání s většinou ostatních použití lineárních programů v diskrétní optimalizace, avšak ilustruje spojení s jinými koncepty.

Vzhledem k orientovanému grafu (PROTI, A) se zdrojovým uzlem s, cílový uzel ta náklady w_ij pro každou hranu (i, j) v A, zvažte program s proměnnými X_ij

minimalizovat

{ displaystyle sum _ {ij v A} w_ {ij} x_ {ij}}

podléhá

{ displaystyle x geq 0}

a pro všechny i,

{ displaystyle sum _ {j} x_ {ij} - sum _ {j} x_ {ji} = { start {případů} 1, & { text {if}} i = s; - 1, & { text {if}} i = t; 0, & { text {jinak.}} end {případy}}}

Je za tím intuice ${ displaystyle x_ {ij}}$ je indikátorová proměnná pro to, zda hrana (i, j) je součástí nejkratší cesty: 1, pokud je, a 0, pokud není. Chceme vybrat sadu hran s minimální hmotností, s výhradou omezení, ze kterého tato sada tvoří cestu s na t (představováno omezením rovnosti: pro všechny vrcholy kromě s a t počet příchozích a odchozích hran, které jsou součástí cesty, musí být stejný (tj. měla by to být cesta od s do t).

Toto LP má speciální vlastnost, že je integrální; konkrétněji každý základní optimální řešení (pokud existuje) má všechny proměnné rovné 0 nebo 1 a množina hran, jejichž proměnné rovné 1 tvoří s-t dipath. Viz Ahuja et al.^[8] pro jeden důkaz, ačkoli vznik tohoto přístupu sahá až do poloviny 20. století.

Duální pro tento lineární program je

maximalizovat y_t − y_s podléhá všem ij, y_j − y_i ≤ w_ij

a proveditelné duály odpovídají konceptu a důsledná heuristika pro Algoritmus * pro nejkratší cesty. Pro jakýkoli proveditelný duální y the snížené náklady ${ displaystyle w '_ {ij} = w_ {ij} -y_ {j} + y_ {i}}$ jsou nezáporné a A* v podstatě běží Dijkstrův algoritmus na tyto snížené náklady.

Obecný algebraický rámec na semirings: problém algebraické cesty

Mnoho problémů lze formulovat jako formu nejkratší cesty pro některé vhodně substituované představy o přidání podél cesty a přijetí minima. Obecným přístupem k nim je považovat tyto dvě operace za operace a semiring. Násobení semiring se provádí podél cesty a přidání je mezi cestami. Tento obecný rámec je znám jako problém algebraické cesty.^[9]^[10]^[11]

Většina klasických algoritmů nejkratší cesty (a nových) může být formulována jako řešení lineárních systémů přes takové algebraické struktury.^[12]

V nedávné době byl pod hlavičkou projektu vytvořen ještě obecnější rámec pro řešení těchto (a mnohem méně zjevně souvisejících problémů) oceňovací algebry.^[13]

Nejkratší cesta ve stochastických časově závislých sítích

V reálných situacích je dopravní síť obvykle stochastická a časově závislá. Cestující, který denně projíždí spojem, může na tomto spoji zaznamenat různé doby cestování, a to nejen kvůli kolísání poptávky po cestování (matice původ - cíl), ale také kvůli takovým incidentům, jako jsou pracovní zóny, špatné povětrnostní podmínky, nehody a poruchy vozidla. . Výsledkem je, že stochastická časově závislá síť (STD) je realističtější reprezentací skutečné silniční sítě ve srovnání s deterministickou.^[14]^[15]

Navzdory značnému pokroku v průběhu posledního desetiletí zůstává kontroverzní otázkou, jak by měla být definována a identifikována optimální cesta ve stochastických silničních sítích. Jinými slovy, neexistuje žádná jedinečná definice optimální cesty za nejistoty. Jednou z možných a běžných odpovědí na tuto otázku je najít cestu s minimální očekávanou dobou cesty. Hlavní výhodou použití tohoto přístupu je, že efektivní algoritmy nejkratší cesty zavedené pro deterministické sítě lze snadno použít k identifikaci cesty s minimální očekávanou dobou cesty ve stochastické síti. Výsledná optimální cesta identifikovaná tímto přístupem však nemusí být spolehlivá, protože tento přístup neřeší variabilitu doby cestování. K řešení tohoto problému někteří vědci používají distribuci času cestování místo jeho očekávané hodnoty, aby zjistili rozdělení pravděpodobnosti celkového času cestování pomocí různých optimalizačních metod, jako je například dynamické programování a Dijkstrův algoritmus .^[16] Tyto metody používají stochastická optimalizace, konkrétně stochastické dynamické programování k nalezení nejkratší cesty v sítích s pravděpodobnou délkou oblouku.^[17] Koncept spolehlivosti doby cestování se v literatuře z oblasti dopravního výzkumu zaměňuje s variabilitou doby cestování, takže lze obecně říci, že čím vyšší je variabilita doby cestování, tím nižší by byla spolehlivost a naopak.

Aby bylo možné přesněji zohlednit spolehlivost doby cestování, byly navrženy dvě společné alternativní definice optimální cesty za nejistoty. Někteří představili koncept nejspolehlivější trasy, jehož cílem je maximalizovat pravděpodobnost příjezdu včas nebo dříve, než je stanovený rozpočet doby cesty. Jiní alternativně předložili koncept spolehlivé dráhy α, na jejímž základě zamýšleli minimalizovat rozpočet doby cesty potřebný k zajištění předem stanovené pravděpodobnosti příjezdu včas.

Viz také

Obousměrné vyhledávání, algoritmus, který najde nejkratší cestu mezi dvěma vrcholy na směrovaném grafu
Euklidovská nejkratší cesta
Síť toku
K nejkratší směrování cesty
Násobení matice min-plus
Hledání cesty
Překlenutí nejkratší cesty
Nejkratší strom cesty

Reference

Poznámky

^ Cormen a kol. 2001, str. 655
^ ^A ^b Dial, Robert B. (1969), „Algoritmus 360: Les s nejkratší cestou s topologickým uspořádáním [H]“, Komunikace ACM, 12 (11): 632–633, doi:10.1145/363269.363610
^ Sanders, Peter (23. března 2009). „Rychlé plánování trasy“. Google Tech Talk. Citovat deník vyžaduje | deník = (Pomoc)
^ Chen, Danny Z. (prosinec 1996). "Vývoj algoritmů a softwaru pro problémy s plánováním geometrické cesty". ACM Computing Surveys. 28 (4es). Článek 18. doi:10.1145/242224.242246. S2CID 11761485.
^ Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. „Rozměr dálnice, nejkratší cesty a prokazatelně efektivní algoritmy“. ACM-SIAM Symposium on Discrete Algorithms, strany 782–793, 2010.
^ Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf „Algoritmus značení podle náboje pro nejkratší cesty v silničních sítích“. Symposium on Experimental Algorithms, strany 230–241, 2011.
^ Kroger, Martin (2005). "Nejkratší vícenásobně odpojená cesta pro analýzu zapletení ve dvou- a trojrozměrných polymerních systémech". Komunikace počítačové fyziky. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016 / j.cpc.2005.01.020.
^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Síťové toky: teorie, algoritmy a aplikace. Prentice Hall. ISBN 978-0-13-617549-0.
^ Pair, Claude (1967), „Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (O algoritmech pro problémy cest v konečných grafech)“, Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) - Theory of Graphs (mezinárodní sympozium), Řím (Itálie), červenec 1966: Dunod (Paříž) et Gordon and Breach (New York), s. 271CS1 maint: umístění (odkaz)
^ Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paříž)
^ Baras, John; Theodorakopoulos, George (4. dubna 2010). Problémy s cestami v sítích. Vydavatelé Morgan & Claypool. str. 9–. ISBN 978-1-59829-924-3.
^ Gondran, Michel; Minoux, Michel (2008). Grafy, dioidy a semirings: nové modely a algoritmy. Springer Science & Business Media. kapitola 4. ISBN 978-0-387-75450-5.
^ Pouly, Marc; Kohlas, Jürg (2011). Obecná inference: Sjednocující teorie pro automatické uvažování. John Wiley & Sons. Kapitola 6. Oceňovací algebry pro problémy s cestami. ISBN 978-1-118-01086-0.
^ Loui, R.P., 1983. Optimální cesty v grafech se stochastickými nebo vícerozměrnými váhami. Komunikace ACM, 26 (9), str. 670-676.
^ Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Víceobjektové nalezení cesty ve stochastických časově závislých silničních sítích pomocí nedominovaného genetického algoritmu třídění". Expertní systémy s aplikacemi. 42 (12): 5056–5064. doi:10.1016 / j.eswa.2015.02.046.
^ Olya, Mohammad Hessam (2014). Msgstr "Nalezení nejkratší cesty v kombinované délce oblouku rozdělení exponenciální - gama pravděpodobnosti rozdělení". International Journal of Operational Research. 21 (1): 25–37. doi:10.1504 / IJOR.2014.064020.
^ Olya, Mohammad Hessam (2014). "Aplikování Dijkstrova algoritmu na obecný problém s nejkratší cestou s délkou oblouku s normální distribucí pravděpodobnosti". International Journal of Operational Research. 21 (2): 143–154. doi:10.1504 / IJOR.2014.064541.

Bibliografie

Ahuja, Ravindra K .; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (Duben 1990). "Rychlejší algoritmy pro problém s nejkratší cestou". Deník ACM. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589.
Bellman, Richard (1958). „O problému se směrováním“. Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090 / qam / 102435. PAN 0102435.
Cherkassky, Boris V .; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Algoritmy nejkratších cest: teorie a experimentální vyhodnocení". Matematické programování. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. PAN 1392160.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Nejkratší cesty jednoho zdroje a nejkratší cesty všech párů". Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. str. 580–642. ISBN 0-262-03293-7.
Dantzig, G. B. (leden 1960). "Na nejkratší trase sítí". Věda o řízení. 6 (2): 187–190. doi:10,1287 / měsíc 6.2.287.
Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paříž)
Dijkstra, E. W. (1959). Msgstr "Poznámka ke dvěma problémům v souvislosti s grafy". Numerische Mathematik. 1: 269–271. doi:10.1007 / BF01386390. S2CID 123284777.
Ford, L. R. (1956). „Teorie toku sítě“. Rand Corporation. P-923. Citovat deník vyžaduje | deník = (Pomoc)
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacciho hromady a jejich použití ve vylepšených algoritmech optimalizace sítě. 25. výroční sympozium o základech informatiky. IEEE. 338–346. doi:10.1109 / SFCS.1984.715934. ISBN 0-8186-0591-X.
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacciho hromady a jejich použití ve vylepšených algoritmech optimalizace sítě". Časopis Asociace pro výpočetní techniku. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
Gabow, H. N. (1983). Msgstr "Škálovací algoritmy pro problémy se sítí". Sborník z 24. výročního symposia o základech informatiky (FOCS 1983) (PDF). 248–258. doi:10.1109 / SFCS.1983.68.
Gabow, Harold N. (1985). Msgstr "Škálovací algoritmy pro problémy se sítí". Journal of Computer and System Sciences. 31 (2): 148–168. doi:10.1016 / 0022-0000 (85) 90039-X. PAN 0828519.
Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P .; Welzl, Emo (eds.). Vylepšené nejkratší cesty na Word RAM. Sborník 27. mezinárodního kolokvia o automatech, jazycích a programování. 61–72. ISBN 978-3-540-67715-4.
Johnson, Donald B. (1977). "Efektivní algoritmy pro nejkratší cesty v řídkých sítích". Deník ACM. 24 (1): 1–13. doi:10.1145/321992.321993. S2CID 207678246.
Johnson, Donald B. (Prosinec 1981). "Prioritní fronta, ve které trvá operace inicializace a fronty $Ó (log log D)$ čas". Teorie matematických systémů. 15 (1): 295–309. doi:10.1007 / BF01786986. PAN 0683047. S2CID 35703411.
Karlsson, Rolf G .; Poblete, Patricio V. (1983). „An $Ó (m log log D)$ "algoritmus pro nejkratší cesty". Diskrétní aplikovaná matematika. 6 (1): 91–93. doi:10.1016 / 0166-218X (83) 90104-X. PAN 0700028.
Leyzorek, M .; Gray, R. S .; Johnson, A. A .; Ladew, W. C .; Meaker, S. R., Jr.; Petry, R. M .; Seitz, R. N. (1957). Vyšetřování modelových technik - první výroční zpráva - 6. června 1956 - 1. července 1957 - studie modelových technik pro komunikační systémy. Cleveland, Ohio: Case Institute of Technology.
Moore, E. F. (1959). "Nejkratší cesta bludištěm". Sborník mezinárodních sympozií o teorii střídání (Cambridge, Massachusetts, 2. – 5. Dubna 1957). Cambridge: Harvard University Press. str. 285–292.
Pettie, Seth; Ramachandran, Vijaya (2002). Výpočet nejkratších cest s porovnáním a přidáním. Sborník z třináctého výročního sympózia ACM-SIAM o diskrétních algoritmech. str.267–276. ISBN 978-0-89871-513-2.
Pettie, Seth (26. ledna 2004). "Nový přístup k nejkratším cestám všech párů na grafech se skutečnou váhou". Teoretická informatika. 312 (1): 47–74. doi:10.1016 / s0304-3975 (03) 00402-x.
Pollack, Maurice; Wiebenson, Walter (březen – duben 1960). „Řešení problému s nejkratší cestou - recenze“. Oper. Res. 8 (2): 224–230. doi:10.1287 / opre.8.2.224. Přiřadí Dijkstrův algoritmus Minty („soukromá komunikace“) na str. 225.
Schrijver, Alexander (2004). Kombinatorická optimalizace - mnohostěn a účinnost. Algoritmy a kombinatorika. 24. Springer. ISBN 978-3-540-20456-5. Zde: vol.A, sect. 7.5b, str. 103
Shimbel, Alfonso (1953). "Strukturální parametry komunikačních sítí". Bulletin of Mathematical Biofhysics. 15 (4): 501–507. doi:10.1007 / BF02476438.
Shimbel, A. (1955). Struktura komunikačních sítí. Sborník ze sympozia o informačních sítích. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. 199–203.
Thorup, Mikkel (1999). "Neusměrněné nejkratší cesty s jedním zdrojem s kladnými celočíselnými váhami v lineárním čase". Deník ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
Thorup, Mikkel (2004). "Fronty priorit s celými čísly s klávesou snížení v konstantním čase a problémem s nejkratšími cestami jednoho zdroje". Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016 / j.jcss.2004.04.003.
Whiting, P. D .; Hillier, J. A. (březen – červen 1960). "Metoda pro nalezení nejkratší trasy silniční sítí". Provozní výzkum čtvrtletně. 11 (1/2): 37–40. doi:10.1057 / jors.1960.32.
Williams, Ryan (2014). "Rychlejší all-pair nejkratší cesty přes složitost obvodu". Sborník 46. výročního sympozia ACM o teorii práce na počítači (STOC '14). New York: ACM. 664–673. arXiv:1312.6680. doi:10.1145/2591796.2591811. PAN 3238994.

Další čtení

Frigioni, D .; Marchetti-Spaccamela, A .; Nanni, U. (1998). Msgstr "Plně dynamický výstup omezený problém s nejkratší cestou jednoho zdroje". Proc. 7. Annu. ACM-SIAM Symp. Diskrétní algoritmy. Atlanta, GA. 212–221. CiteSeerX 10.1.1.32.9856.
Dreyfus, S.E. (říjen 1967). Posouzení některých algoritmů nejkratší cesty (PDF) (Zpráva). Projekt Rand. United States Air Force. RM-5433-PR. DTIC AD-661265.

[1] Cormen a kol. 2001, str. 655

[dial69-2] A ^b Dial, Robert B. (1969), „Algoritmus 360: Les s nejkratší cestou s topologickým uspořádáním [H]“, Komunikace ACM, 12 (11): 632–633, doi:10.1145/363269.363610

[3] Sanders, Peter (23. března 2009). „Rychlé plánování trasy“. Google Tech Talk. Citovat deník vyžaduje | deník = (Pomoc)

[4] Chen, Danny Z. (prosinec 1996). "Vývoj algoritmů a softwaru pro problémy s plánováním geometrické cesty". ACM Computing Surveys. 28 (4es). Článek 18. doi:10.1145/242224.242246. S2CID 11761485.

[5] Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. „Rozměr dálnice, nejkratší cesty a prokazatelně efektivní algoritmy“. ACM-SIAM Symposium on Discrete Algorithms, strany 782–793, 2010.

[6] Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf „Algoritmus značení podle náboje pro nejkratší cesty v silničních sítích“. Symposium on Experimental Algorithms, strany 230–241, 2011.

[7] Kroger, Martin (2005). "Nejkratší vícenásobně odpojená cesta pro analýzu zapletení ve dvou- a trojrozměrných polymerních systémech". Komunikace počítačové fyziky. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. doi:10.1016 / j.cpc.2005.01.020.

[8] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Síťové toky: teorie, algoritmy a aplikace. Prentice Hall. ISBN 978-0-13-617549-0.

[Pair1966-9] Pair, Claude (1967), „Sur des algorithmes pour des problèmes de cheminement dans les graphes finis (O algoritmech pro problémy cest v konečných grafech)“, Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) - Theory of Graphs (mezinárodní sympozium), Řím (Itálie), červenec 1966: Dunod (Paříž) et Gordon and Breach (New York), s. 271CS1 maint: umístění (odkaz)

[10] Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Path Problems in Graphs), Dunod (Paříž)

[BarasTheodorakopoulos2010-11] Baras, John; Theodorakopoulos, George (4. dubna 2010). Problémy s cestami v sítích. Vydavatelé Morgan & Claypool. str. 9–. ISBN 978-1-59829-924-3.

[GondranMinoux2008-12] Gondran, Michel; Minoux, Michel (2008). Grafy, dioidy a semirings: nové modely a algoritmy. Springer Science & Business Media. kapitola 4. ISBN 978-0-387-75450-5.

[PoulyKohlas2012-13] Pouly, Marc; Kohlas, Jürg (2011). Obecná inference: Sjednocující teorie pro automatické uvažování. John Wiley & Sons. Kapitola 6. Oceňovací algebry pro problémy s cestami. ISBN 978-1-118-01086-0.

[14] Loui, R.P., 1983. Optimální cesty v grafech se stochastickými nebo vícerozměrnými váhami. Komunikace ACM, 26 (9), str. 670-676.

[15] Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Víceobjektové nalezení cesty ve stochastických časově závislých silničních sítích pomocí nedominovaného genetického algoritmu třídění". Expertní systémy s aplikacemi. 42 (12): 5056–5064. doi:10.1016 / j.eswa.2015.02.046.

[16] Olya, Mohammad Hessam (2014). Msgstr "Nalezení nejkratší cesty v kombinované délce oblouku rozdělení exponenciální - gama pravděpodobnosti rozdělení". International Journal of Operational Research. 21 (1): 25–37. doi:10.1504 / IJOR.2014.064020.

[17] Olya, Mohammad Hessam (2014). "Aplikování Dijkstrova algoritmu na obecný problém s nejkratší cestou s délkou oblouku s normální distribucí pravděpodobnosti". International Journal of Operational Research. 21 (2): 143–154. doi:10.1504 / IJOR.2014.064541.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]