Problem najkrótszej ścieżki - Shortest path problem
W teorii wykres The problem najkrótszej ścieżki jest problem znalezienia drogi między dwoma wierzchołkami (lub węzłów) w wykresie tak, że suma wag jej krawędzie składowych jest zminimalizowane.
Problem znalezienia najkrótszej ścieżki pomiędzy dwoma skrzyżowaniami na mapie drogowej można zamodelować jako szczególny przypadek problemu najkrótszej ścieżki w grafach, gdzie wierzchołki odpowiadają skrzyżowaniom, a krawędzie odpowiadają odcinkom drogi, z których każdy jest ważony długością człon.
Definicja
Najkrótsza ścieżka problemu może być określona na wykresie czy nieukierunkowane , skierowanych lub zmieszane . Jest tu zdefiniowany dla grafów nieskierowanych; dla grafów skierowanych definicja ścieżki wymaga, aby kolejne wierzchołki były połączone odpowiednią krawędzią skierowaną.
Dwa wierzchołki sąsiadują ze sobą, gdy oba leżą na wspólnej krawędzi. Ścieżki w nieukierunkowane wykresu jest sekwencja wierzchołków , tak że sąsiaduje z . Taka ścieżka nazywana jest ścieżką o długości od do . ( Są zmienne; ich numeracja odnosi się tutaj do ich pozycji w sekwencji i nie musi odnosić się do żadnego kanonicznego etykietowania wierzchołków.)
Niech będzie incydentem krawędziowym dla obu i . Biorąc pod uwagę funkcję wagi o wartościach rzeczywistych i nieskierowany (prosty) wykres , najkrótsza ścieżka od do jest ścieżką (gdzie i ), która ze wszystkich możliwych minimalizuje sumę. Gdy każda krawędź na wykresie ma wagę jednostkową lub , jest to równoważne znalezienie ścieżki z najmniejszą liczbą krawędzi.
Problem jest również czasami nazywany problemem najkrótszej ścieżki pojedynczej pary , aby odróżnić go od następujących odmian:
- Problem najkrótszej ścieżki single-source , w którym musimy znaleźć najkrótsze ścieżki ze źródła wierzchołka v do wszystkich pozostałych wierzchołków w grafie.
- Problem najkrótszej ścieżki jednego przeznaczenia , w którym musimy znaleźć najkrótsze ścieżki ze wszystkich wierzchołków grafu skierowanego do jednego przeznaczenia wierzchołka v . Można to zredukować do problemu najkrótszej ścieżki z jednym źródłem, odwracając łuki w grafie skierowanym.
- Problem najkrótszej ścieżki dla wszystkich par , w którym musimy znaleźć najkrótsze ścieżki pomiędzy każdą parą wierzchołków v , v' na wykresie.
Te uogólnienia mają znacznie bardziej wydajne algorytmy niż uproszczone podejście polegające na uruchomieniu algorytmu najkrótszej ścieżki z pojedynczą parą na wszystkich odpowiednich parach wierzchołków.
Algorytmy
Najważniejsze algorytmy rozwiązania tego problemu to:
- Algorytm Dijkstry rozwiązuje problem najkrótszej ścieżki z jednym źródłem z nieujemną wagą krawędzi.
- Algorytm Bellmana-Forda rozwiązuje problem pojedynczego źródła, jeśli wagi krawędzi mogą być ujemne.
- Algorytm wyszukiwania A* rozwiązuje najkrótszą ścieżkę dla pojedynczej pary przy użyciu heurystyki, aby przyspieszyć wyszukiwanie.
- Algorytm Floyda-Warshalla rozwiązuje wszystkie pary najkrótszych ścieżek.
- Algorytm Johnsona rozwiązuje wszystkie pary najkrótszych ścieżek i może być szybszy niż Floyd-Warshall na rzadkich grafach .
- Algorytm Viterbiego rozwiązuje problem najkrótszej ścieżki stochastycznej z dodatkową wagą probabilistyczną na każdym węźle.
Dodatkowe algorytmy i związane z nimi oceny można znaleźć w Cherkassky, Goldberg i Radzik (1996) .
Najkrótsze ścieżki z jednego źródła
Wykresy nieskierowane
Wagi | Złożoność czasowa | Autor |
---|---|---|
ℝ + | O ( V 2 ) | Dijkstra 1959 |
ℝ + | O (( E + V ) log V ) | Johnson 1977 ( sterta binarna ) |
ℝ + | O ( E + V log V ) | Fredman & Tarjan 1984 ( sterta Fibonacciego ) |
ℕ | O ( E ) | Thorup 1999 (wymaga mnożenia w czasie stałym) |
Wykresy nieważone
Algorytm | Złożoność czasowa | Autor |
---|---|---|
Wyszukiwanie wszerz | O ( E + V ) |
Skierowane grafy acykliczne (DAG)
Algorytm wykorzystujący sortowanie topologiczne może rozwiązać problem najkrótszej ścieżki z jednym źródłem w czasie Θ( E + V ) w arbitralnie ważonych DAG-ach.
Wykresy skierowane z wagami nieujemnymi
Poniższa tabela pochodzi z Schrijver (2004) , z pewnymi poprawkami i uzupełnieniami. Zielone tło wskazuje asymptotycznie najlepsze ograniczenie w tabeli; L to maksymalna długość (lub waga) między wszystkimi krawędziami, przy założeniu całkowitej wagi krawędzi.
Wagi | Algorytm | Złożoność czasowa | Autor |
---|---|---|---|
ℝ | O ( V 2 EL ) | Ford 1956 | |
ℝ | Algorytm Bellmana-Forda | O ( VE ) | Shimbel 1955 , Bellman 1958 , Moore 1959 |
ℝ | O ( V 2 log V ) | Dantzig 1960 | |
ℝ | Algorytm Dijkstry z listą | O ( V 2 ) | Leyzorek i in. 1957 , Dijkstra 1959 , Minty (patrz Pollack i Wiebenson 1960 ), Whiting i Hillier 1960 |
ℝ | Algorytm Dijkstry ze stertą binarną | O (( E + V ) log V ) | Johnson 1977 |
ℝ | Algorytm Dijkstry ze stertą Fibonacciego | O ( E + V log V ) | Fredman i Tarjan 1984 , Fredman i Tarjan 1987 |
ℕ | Algorytm wybierania ( algorytm Dijkstry wykorzystujący kolejkę kubełkową z kubełkami L ) | O ( E + LV ) | Wybierz numer 1969 |
O ( E log log L ) | Johnson 1981 , Karlsson i Poblete 1983 | ||
Algorytm Gabowa | O ( E log E / V L ) | Gabów 1983 , Gabów 1985 | |
O ( E + V √ log L ) | Ahuja i in. 1990 | ||
Thorup | O ( E + V log log V ) | Thorup 2004 |
Wykresy ukierunkowane z dowolnymi wagami bez cykli ujemnych
Wagi | Algorytm | Złożoność czasowa | Autor |
---|---|---|---|
ℝ | O ( V 2 EL ) | Ford 1956 | |
ℝ | Algorytm Bellmana-Forda | O ( VE ) | Shimbel 1955 , Bellman 1958 , Moore 1959 |
ℝ | Johnson-Dijkstra ze stertą binarną | O ( V ( E + log V )) | Johnson 1977 |
ℝ | Johnson-Dijkstra ze stertą Fibonacciego | O ( V ( E + log V )) | Fredman & Tarjan 1984 , Fredman & Tarjan 1987 , adaptacja wg Johnsona 1977 |
ℕ | Technika Johnsona zastosowana do algorytmu Diala | O ( V ( E + L )) | Tarcza 1969 , adaptacja wg Johnsona 1977 |
Planarne grafy skierowane z dowolnymi wagami
Wszystkie pary najkrótsze ścieżki
Problem najkrótszej ścieżki dla wszystkich par znajduje najkrótsze ścieżki pomiędzy każdą parą wierzchołków v , v' na wykresie. Problem najkrótszych ścieżek składających się z wszystkich par dla nieważonych grafów skierowanych został wprowadzony przez Shimbel (1953) , który zaobserwował, że można go rozwiązać za pomocą liniowej liczby mnożeń macierzy, która zajmuje łączny czas O ( V 4 ) .
Wykres nieskierowany
Wagi | Złożoność czasowa | Algorytm |
---|---|---|
ℝ + | O ( V 3 ) | Algorytm Floyda-Warshalla |
Algorytm Seidela (przewidywany czas działania) | ||
ℕ | Williams 2014 | |
ℝ + | O ( EV log α ( E , V )) | Pettie i Ramachandran 2002 |
ℕ | O ( EV ) | Thorup 1999 zastosował się do każdego wierzchołka (wymaga mnożenia w czasie stałym). |
Kierowany wykres
Wagi | Złożoność czasowa | Algorytm |
---|---|---|
ℝ (brak cykli ujemnych) | O ( V 3 ) | Algorytm Floyda-Warshalla |
ℕ | Williams 2014 | |
ℝ (brak cykli ujemnych) | O ( EV + V 2 log V ) | Johnson–Dijkstra |
ℝ (brak cykli ujemnych) | O ( EV + V 2 log log V ) | Mały 2004 |
ℕ | O ( EV + V 2 log log V ) | Hagerup 2000 |
Aplikacje
Algorytmy najkrótszej ścieżki są stosowane do automatycznego znajdowania wskazówek dojazdu między fizycznymi lokalizacjami, takich jak wskazówki dojazdu w witrynach map internetowych, takich jak MapQuest lub Google Maps . Dla tej aplikacji dostępne są szybkie wyspecjalizowane algorytmy.
Jeśli przedstawić niedeterministyczną maszynę abstrakcyjną jako graf, w którym wierzchołki opisują stany, a krawędzie opisują możliwe przejścia, algorytmy najkrótszej ścieżki można wykorzystać do znalezienia optymalnej sekwencji wyborów, aby osiągnąć określony stan docelowy lub do ustalenia dolnych granic czasu potrzebnego do osiągnąć dany stan. Na przykład, jeśli wierzchołki reprezentują stany łamigłówki, takie jak kostka Rubika, a każda skierowana krawędź odpowiada pojedynczemu ruchowi lub zwrotowi, algorytmy najkrótszej ścieżki mogą być użyte do znalezienia rozwiązania, które wykorzystuje minimalną możliwą liczbę ruchów.
W myśleniu o sieci lub telekomunikacji ten problem z najkrótszą ścieżką jest czasami nazywany problemem minimalnego opóźnienia i zwykle wiąże się z problemem najszerszej ścieżki . Na przykład algorytm może szukać najkrótszej (min-opóźnienie) najszerszej ścieżki lub najszerszej najkrótszej (min-opóźnienie) ścieżki.
Bardziej beztroskim zastosowaniem są gry „ sześć stopni separacji ”, które próbują znaleźć najkrótszą ścieżkę na wykresach, tak jak gwiazdy filmowe pojawiające się w tym samym filmie.
Inne zastosowania, często badane w badaniach operacyjnych , obejmują rozplanowanie zakładów i obiektów, robotykę , transport i projektowanie VLSI .
Sieci drogowe
Sieć drogową można traktować jako wykres o dodatnich wagach. Węzły reprezentują skrzyżowania dróg, a każda krawędź wykresu jest powiązana z fragmentem drogi między dwoma skrzyżowaniami. Waga krawędzi może odpowiadać długości powiązanego odcinka drogi, czasowi przebycia odcinka lub kosztowi przejechania odcinka. Wykorzystując skierowane krawędzie możliwe jest również modelowanie ulic jednokierunkowych. Takie wykresy są szczególne w tym sensie, że niektóre krawędzie są ważniejsze niż inne w przypadku podróży na duże odległości (np. autostrady). Właściwość ta została sformalizowana za pomocą pojęcia wymiaru autostrady. Istnieje wiele algorytmów, które wykorzystują tę właściwość i dlatego są w stanie obliczyć najkrótszą ścieżkę znacznie szybciej niż byłoby to możliwe na ogólnych grafach.
Wszystkie te algorytmy działają w dwóch fazach. W pierwszej fazie graf jest wstępnie przetwarzany bez znajomości węzła źródłowego lub docelowego. Druga faza to faza zapytania. W tej fazie znany jest węzeł źródłowy i docelowy. Pomysł polega na tym, że sieć drogowa jest statyczna, więc faza przetwarzania wstępnego może być wykonana raz i wykorzystana dla dużej liczby zapytań w tej samej sieci drogowej.
Algorytm o najszybszym znanym czasie zapytania nazywa się etykietowaniem piasty i jest w stanie obliczyć najkrótszą ścieżkę w sieci drogowej Europy lub USA w ułamku mikrosekundy. Inne techniki, które zostały użyte to:
- ALT ( wyszukiwanie A* , punkty orientacyjne i nierówność trójkątów )
- Flagi łukowe
- Hierarchie skurczowe
- Routing węzłów tranzytowych
- Przycinanie oparte na zasięgu
- Etykietowanie
- Etykiety piasty
Powiązane problemy
Aby poznać problemy z najkrótszą ścieżką w geometrii obliczeniowej , zobacz Najkrótsza ścieżka euklidesowa .
Problem komiwojażera jest problemem znalezienie najkrótszej drogi, która przechodzi przez każdy wierzchołek dokładnie raz i wraca do początku. W przeciwieństwie do problemu najkrótszej ścieżki, który można rozwiązać w czasie wielomianowym na grafach bez cykli ujemnych, problem komiwojażera jest NP-zupełny i jako taki uważa się, że nie można go skutecznie rozwiązać dla dużych zbiorów danych (patrz problem P = NP ). Problem znalezienia najdłuższej ścieżki w grafie jest również NP-zupełny.
Problem kanadyjskiego podróżnika i stochastyczny problem najkrótszej ścieżki to uogólnienia, w których albo graf nie jest w pełni znany osobie poruszającej się, zmienia się w czasie, albo gdzie działania (przejścia) są probabilistyczne.
Najkrótsza wielokrotna rozłączona ścieżka jest reprezentacją sieci ścieżek pierwotnych w ramach teorii Reptacji .
Problem z najszerszą ścieżką polega na szukaniu takiej ścieżki, aby minimalna etykieta dowolnej krawędzi była jak największa.
Strategiczne najkrótsze ścieżki
Czasami krawędzie grafu mają osobowości: każda krawędź ma swój własny, egoistyczny interes. Przykładem jest sieć komunikacyjna, w której każda krawędź jest komputerem, który prawdopodobnie należy do innej osoby. Różne komputery mają różne prędkości transmisji, więc każda krawędź w sieci ma wagę liczbową równą liczbie milisekund potrzebnych do przesłania wiadomości. Naszym celem jest wysłanie wiadomości pomiędzy dwoma punktami w sieci w jak najkrótszym czasie. Jeśli znamy czas transmisji każdego komputera (wagę każdej krawędzi), możemy użyć standardowego algorytmu najkrótszych ścieżek. Jeśli nie znamy czasów transmisji, musimy poprosić każdy komputer, aby podał nam swój czas transmisji. Ale komputery mogą być samolubne: komputer może nam powiedzieć, że jego czas transmisji jest bardzo długi, abyśmy nie zawracali mu głowy naszymi wiadomościami. Możliwym rozwiązaniem tego problemu jest zastosowanie wariantu mechanizmu VCG , który daje komputerom zachętę do ujawniania swoich prawdziwych wag.
Formuła programowania liniowego
Poniżej przedstawiono naturalne sformułowanie programowania liniowego dla problemu najkrótszej ścieżki. Jest to bardzo proste w porównaniu do większości innych zastosowań programów liniowych w optymalizacji dyskretnej , jednak ilustruje połączenia z innymi koncepcjami.
Mając graf skierowany ( V , A ) z węzłem źródłowym s , węzłem docelowym t i kosztem w ij dla każdej krawędzi ( i , j ) w A , rozważ program ze zmiennymi x ij
- zminimalizować temat i dla wszystkich i ,
Intuicja kryjąca się za tym jest taka, że jest to zmienna wskazująca, czy krawędź ( i , j ) jest częścią najkrótszej ścieżki: 1, gdy jest, i 0, jeśli nie jest. Chcemy wybrać zbiór krawędzi o minimalnej wadze, z zastrzeżeniem, że ten zbiór tworzy ścieżkę od s do t (reprezentowaną przez ograniczenie równości: dla wszystkich wierzchołków z wyjątkiem s i t liczba krawędzi wchodzących i wychodzących, które są częścią ścieżki musi być taka sama (tzn. powinna być ścieżką od s do t).
Ten LP ma tę szczególną właściwość, że jest integralny; dokładniej, każde podstawowe rozwiązanie optymalne (jeśli takie istnieje) ma wszystkie zmienne równe 0 lub 1, a zbiór krawędzi, których zmienne równe 1, tworzą dwuścieżkę s - t . Patrz Ahuja i in. za jeden dowód, choć początki tego podejścia sięgają połowy XX wieku.
Dual dla tego programu liniowego to
- maksymalizuj y t − y s podlegające dla wszystkich ij , y j − y i ≤ w ij
a wykonalne dualności odpowiadają koncepcji spójnej heurystyki dla algorytmu A* dla najkrótszych ścieżek. Dla każdego możliwego podwójnego y na niższe koszty są nieujemne i A * w zasadzie przebiega Algorytm Dijkstry na tych obniżonych kosztach.
Ogólne ramy algebraiczne na półpierścieniach: problem ścieżki algebraicznej
Wiele problemów można sformułować jako formę najkrótszej ścieżki dla pewnych odpowiednio podstawionych pojęć dodawania wzdłuż ścieżki i przyjmowania minimum. Ogólne podejście do nich polega na uznaniu tych dwóch operacji za operacje semiringu . Mnożenie semiringów odbywa się wzdłuż ścieżki, a dodawanie między ścieżkami. Te ogólne ramy są znane jako problem ścieżki algebraicznej .
Większość klasycznych algorytmów najkrótszej ścieżki (i nowych) można sformułować jako rozwiązywanie układów liniowych na takich strukturach algebraicznych.
Niedawno, pod hasłem algebr wyceny , opracowano jeszcze bardziej ogólne ramy rozwiązywania tych (i znacznie mniej wyraźnie powiązanych problemów) .
Najkrótsza ścieżka w stochastycznych sieciach zależnych od czasu
W rzeczywistych sytuacjach sieć transportowa jest zwykle stochastyczna i zależna od czasu. W rzeczywistości podróżny korzystający z łącza codziennie może doświadczać różnych czasów podróży na tym łączu nie tylko ze względu na wahania popytu na podróże (matryca pochodzenie-miejsce docelowe), ale także z powodu takich zdarzeń, jak strefy pracy, złe warunki pogodowe, wypadki i awarie pojazdów. . W rezultacie sieć stochastyczna zależna od czasu (STD) jest bardziej realistyczną reprezentacją rzeczywistej sieci drogowej w porównaniu z siecią deterministyczną.
Pomimo znacznego postępu w ciągu ostatniej dekady, kontrowersyjnym pytaniem pozostaje, jak należy zdefiniować i zidentyfikować optymalną ścieżkę w stochastycznych sieciach drogowych. Innymi słowy, nie ma unikalnej definicji optymalnej ścieżki w warunkach niepewności. Jedną z możliwych i powszechnych odpowiedzi na to pytanie jest znalezienie trasy o minimalnym przewidywanym czasie podróży. Główną zaletą zastosowania tego podejścia jest to, że efektywne algorytmy najkrótszej ścieżki wprowadzone dla sieci deterministycznych mogą być łatwo zastosowane do identyfikacji ścieżki o minimalnym oczekiwanym czasie podróży w sieci stochastycznej. Jednak uzyskana optymalna ścieżka zidentyfikowana przez to podejście może nie być wiarygodna, ponieważ podejście to nie uwzględnia zmienności czasu podróży. Aby rozwiązać ten problem, niektórzy badacze wykorzystują rozkład czasu podróży zamiast jego oczekiwanej wartości, aby znaleźć rozkład prawdopodobieństwa całkowitego czasu podróży przy użyciu różnych metod optymalizacji, takich jak programowanie dynamiczne i algorytm Dijkstry . Metody te wykorzystują optymalizację stochastyczną , w szczególności stochastyczne programowanie dynamiczne, aby znaleźć najkrótszą ścieżkę w sieciach o probabilistycznej długości łuku. Pojęcie niezawodności czasu podróży jest używane zamiennie ze zmiennością czasu podróży w literaturze dotyczącej transportu, tak że generalnie można powiedzieć, że im większa zmienność czasu podróży, tym niższa byłaby niezawodność i odwrotnie.
Aby dokładniej uwzględnić niezawodność czasu podróży, zaproponowano dwie wspólne alternatywne definicje optymalnej ścieżki w warunkach niepewności. Niektórzy wprowadzili koncepcję najbardziej niezawodnej ścieżki, której celem jest maksymalizacja prawdopodobieństwa dotarcia na czas lub wcześniej niż określony budżet czasu podróży. Inni, alternatywnie, wysunęli koncepcję trasy niezawodnej α, na podstawie której zamierzali zminimalizować budżet czasu podróży wymagany do zapewnienia określonego z góry prawdopodobieństwa przyjazdu na czas.
Zobacz też
- Wyszukiwanie dwukierunkowe , algorytm, który znajduje najkrótszą ścieżkę między dwoma wierzchołkami na skierowanym grafie
- Najkrótsza ścieżka euklidesowa
- Sieć przepływu
- K trasowanie najkrótszej ścieżki
- Mnożenie macierzy min-plus
- Znalezienie drogi
- Mostkowanie najkrótszej ścieżki
- Drzewo najkrótszej ścieżki
Bibliografia
Uwagi
Bibliografia
- Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlina, Jakuba; Tarjan, Robert E. (kwiecień 1990). „Szybsze algorytmy dla problemu najkrótszej ścieżki” . Dziennik ACM . ACM. 37 (2): 213–223. doi : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID 5499589 .
- Bellman, Richard (1958). „W przypadku problemu z routingiem” . Kwartalnik Matematyki Stosowanej . 16 : 87–90. doi : 10.1090/qam/102435 . MR 0102435 .
- Czerkaski, Borys V.; Goldberg, Andrew V. ; Radzik, Tomasz (1996). "Algorytmy najkrótszych ścieżek: teoria i ocena eksperymentalna" . Programowanie matematyczne . Ser. A. 73 (2): 129–174. doi : 10.1016/0025-5610(95)00021-6 . MR 1392160 .
- Cormen, Thomas H .; Leiserson, Charles E. ; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. „Najkrótsze ścieżki z jednym źródłem i wszystkie pary najkrótsze ścieżki”. Wprowadzenie do algorytmów (wyd. 2). MIT Press i McGraw-Hill. s. 580–642. Numer ISBN 0-262-03293-7.
- Dantzig, Wielka Brytania (styczeń 1960). „Na najkrótszej trasie przez sieć”. Nauka o zarządzaniu . 6 (2): 187–190. doi : 10.1287/mnsc.6.2.187 .
- Derniame, Jean Claude; Pair, Claude (1971), Problèmes de cheminement dans les graphes (Problemy ścieżki na wykresach) , Dunod (Paryż)
- Dijkstra, EW (1959). „Uwaga na dwa problemy w związku z wykresami”. Matematyka numeryczna . 1 : 269–271. doi : 10.1007/BF01386390 . S2CID 123284777 .
-
Ford, LR (1956). „Teoria przepływu w sieci” . Rand Corporation. P-923. Cytowanie dziennika wymaga
|journal=
( pomoc ) - Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Sterty Fibonacciego i ich zastosowania w ulepszonych algorytmach optymalizacji sieci . 25. Doroczne Sympozjum Podstaw Informatyki. IEEE . s. 338-346. doi : 10.1109/SFCS.1984.715934 . Numer ISBN 0-8186-0591-X.
- Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). „Kaps Fibonacciego i ich zastosowania w ulepszonych algorytmach optymalizacji sieci”. Czasopismo Stowarzyszenia Maszyn Komputerowych . 34 (3): 596–615. doi : 10.1145/28869.28874 . S2CID 7904683 .
- Gabow, HN (1983). „Algorytmy skalowania problemów sieciowych”. Materiały z 24. dorocznego Sympozjum Podstaw Informatyki (FOCS 1983) (PDF) . s. 248-258. doi : 10.1109/SFCS.1983.68 .
- Gabow, Harold N. (1985). „Algorytmy skalowania problemów sieciowych” . Journal of Computer and System Sciences . 31 (2): 148–168. doi : 10.1016/0022-0000(85)90039-X . MR 0828519 .
- Hagerup, Torben (2000). Montanari, Ugo; Rolim, José DP; Welzl, Emo (wyd.). Ulepszone najkrótsze ścieżki w pamięci RAM programu Word . Materiały 27. Międzynarodowego Kolokwium Automatyki, Języków i Programowania . s. 61-72. Numer ISBN 978-3-540-67715-4.
- Johnson, Donald B. (1977). „Skuteczne algorytmy dla najkrótszych ścieżek w rzadkich sieciach”. Dziennik ACM . 24 (1): 1–13. doi : 10.1145/321992.321993 . S2CID 207678246 .
- Altıntaş, Gökhan (2020). Dokładne rozwiązania problemów z najkrótszą drogą na podstawie analogii mechanicznych: w połączeniu z labiryntami . Amazon Digital Services LLC. str. 97. Numer ISBN 9798655831896.
- Johnson, Donald B. (grudzień 1981). „Kolejka priorytetowa, w której operacje inicjalizacji i kolejki zajmują czas O (dziennik D ) ”. Teoria systemów matematycznych . 15 (1): 295–309. doi : 10.1007/BF01786986 . MR 0683047 . S2CID 35703411 .
- Karlsson, Rolf G.; Poblete, Patricio V. (1983). „ Algorytm O ( m log log D ) dla najkrótszych ścieżek” . Dyskretna matematyka stosowana . 6 (1): 91-93. doi : 10.1016/0166-218X(83)90104-X . MR 0700028 .
- Leyzorek M.; Szary, RS; Johnsona, AA; Lade, WC; Meaker, SR, Jr.; Petry, RM; Seitz, RN (1957). Badanie technik modelowych — pierwszy raport roczny — 6 czerwca 1956 — 1 lipca 1957 — studium modelowych technik systemów komunikacyjnych . Cleveland, Ohio: Case Institute of Technology.
- Moore, EF (1959). „Najkrótsza droga przez labirynt”. Materiały z międzynarodowego sympozjum na temat teorii przełączania (Cambridge, Massachusetts, 2-5 kwietnia 1957) . Cambridge: Wydawnictwo Uniwersytetu Harvarda. s. 285–292.
- Mały, Seth; Ramachandran, Widźaja (2002). Obliczanie najkrótszych ścieżek z porównaniami i dodatkami . Materiały z XIII Dorocznego Sympozjum ACM-SIAM nt . algorytmów dyskretnych . s. 267–276 . Numer ISBN 978-0-89871-513-2.
- Pettie, Seth (26 stycznia 2004). „Nowe podejście do wszystkich par najkrótszych ścieżek na wykresach ważonych realnie” . Informatyka teoretyczna . 312 (1): 47–74. doi : 10.1016/s0304-3975(03)00402-x .
- Pollack, Maurycy; Wiebenson, Walter (marzec-kwiecień 1960). „Rozwiązanie problemu najkrótszej trasy-przegląd”. Oper. Res . 8 (2): 224–230. doi : 10.1287/opre.8.2.224 . Przypisuje algorytm Dijkstry Minty („komunikacja prywatna”) na s. 225.
- Schrijver, Aleksander (2004). Optymalizacja kombinatoryczna — wielościany i wydajność . Algorytmy i kombinatoryka. 24 . Skoczek. Numer ISBN 978-3-540-20456-5.Tutaj: t.A, rozdz.7.5b, s. 103
- Shimbel, Alfonso (1953). „Parametry strukturalne sieci komunikacyjnych”. Biuletyn Biofizyki Matematycznej . 15 (4): 501–507. doi : 10.1007/BF02476438 .
- Shimbel, A. (1955). Struktura w sieciach komunikacyjnych . Materiały z Sympozjum Sieci Informacyjnych. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. s. 199–203.
- Thorup, Mikkel (1999). „Nieskierowane najkrótsze ścieżki z jednego źródła z dodatnimi wagami całkowitymi w czasie liniowym”. Dziennik ACM . 46 (3): 362–394. doi : 10.1145/316542.316548 . S2CID 207654795 .
- Thorup, Mikkel (2004). "Całkowite priorytety kolejek z kluczem zmniejszania w stałym czasie i problem najkrótszych ścieżek z jednego źródła" . Journal of Computer and System Sciences . 69 (3): 330–353. doi : 10.1016/j.jcss.2004.04.003 .
- Witlinek, PD; Hillier, JA (marzec-czerwiec 1960). „Metoda znajdowania najkrótszej trasy przez sieć drogową”. Kwartalnik Badań Operacyjnych . 11 (1/2): 37-40. doi : 10.1057/jors.1960.32 .
- Williams, Ryan (2014). „Szybsze wszystkie pary najkrótsze ścieżki dzięki złożoności obwodu”. Materiały z 46. dorocznego sympozjum ACM na temat teorii informatyki (STOC '14) . Nowy Jork: ACM. s. 664–673. arXiv : 1312.6680 . doi : 10.1145/2591796.2591811 . MR 3238994 .
Dalsza lektura
- Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). „W pełni dynamiczne wyjście ograniczone jednym źródłem problem najkrótszej ścieżki”. Proc. VII rocz. ACM-SIAM Symp. Algorytmy dyskretne . Atlanta, GA. s. 212-221. CiteSeerX 10.1.1.32.9856 .
- Dreyfus, SE (październik 1967). Ocena niektórych algorytmów najkrótszej ścieżki (PDF) (raport). Projekt Rand. Siły Powietrzne Stanów Zjednoczonych. RM-5433-PR. DTIC AD-661265.