Kürzestes Pfadproblem

Kürzester Weg (a, c, e, d, f) zwischen den Scheitelpunkten A und F im gewichteten gerichteten Diagramm

Im Graphentheorie, das kürzestes Pfadproblem ist das Problem, a zu finden Weg zwischen zwei Eckpunkte (oder Knoten) in a Graph so dass die Summe der Gewichte seiner Bestandteile werden minimiert.

Das Problem, den kürzesten Pfad zwischen zwei Kreuzungen auf einer Roadmap zu finden Segment.

Definition

Das kürzeste Pfadproblem kann definiert werden für Grafiken ob ungerichtet, gerichtet, oder gemischt. Es ist hier für ungerichtete Graphen definiert; Für gerichtete Graphen erfordert die Definition des Pfades, dass aufeinanderfolgende Eckpunkte durch eine geeignete gerichtete Kante verbunden sind.

Zwei Scheitelpunkte sind nebeneinander, wenn beide einer gemeinsamen Kante fällt. EIN Weg In einer ungerichteten Grafik ist a Reihenfolge von Scheitelpunkten $oder$ so dass ${\ displayStyle v_ {i}}$ ist neben ${\ displayStyle v_ {i+1}}$ zum ${\ displayStyle 1 \ leq i <n}$ . Ein solcher Weg ${\ displayStyle p}$ wird als Weg der Länge bezeichnet ${\ displayStyle n-1}$ aus ${\ displayStyle v_ {1}}$ zu ${\ displayStyle v_ {n}}$ . (Das ${\ displayStyle v_ {i}}$ sind Variablen; Ihre Nummerierung bezieht sich hier auf ihre Position in der Sequenz und muss sich nicht auf kanonische Kennzeichnung der Eckpunkte beziehen.)

Lassen ${\ displayStyle e_ {i, j}}$ Sei der Rand, der beides vorkommt ${\ displayStyle v_ {i}}$ und ${\ displayStyle v_ {j}}$ . Angenommen echt bewertet Gewichtsfunktion ${\ displayStyle f: e \ rightarrow \ mathbb {r}}$ und eine ungerichtete (einfache) Grafik ${\ displayStyle g}$ , der kürzeste Weg von ${\ displayStyle v}$ zu ${\ displayStyle v '}$ ist der Weg ${\ displayStyle p = (v_ {1}, v_ {2}, \ ldots, v_ {n})}$ (wo ${\ displayStyle v_ {1} = v}$ und ${\ displayStyle v_ {n} = v '}$ ) das über alles möglich ${\ displayStyle n}$ minimiert die Summe ${\ displayStyle \ sum _ {i = 1}^{n-1} f (e_ {i, i+1}).}$ Wenn jede Kante im Diagramm ein Einheitsgewicht hat oder ${\ displayStyle f: e \ rightarrow \ {1 \}}$ Dies ist gleichbedeutend damit, den Weg mit den wenigsten Kanten zu finden.

Das Problem wird manchmal auch als genannt Ein-Pair-kürzester Pfadproblem, um es von den folgenden Variationen zu unterscheiden:

Das kürzeste Pfadproblem mit einem Source, in dem wir kürzeste Wege von einem Quellscheitelpunkt finden müssen v zu allen anderen Scheitelpunkten in der Grafik.
Das Ein- und Destinationskürzestes Problem, in dem wir kürzeste Wege von allen Scheitelpunkten im gerichteten Diagramm zu einem einzelnen Zielscheitelpunkt finden müssen v. Dies kann auf das kürzeste Einstiegsproblem reduziert werden, indem die Bögen im gerichteten Diagramm umgekehrt werden.
Das All-Pairs kürzestes Pfadproblem, in dem wir kürzeste Wege zwischen jedem Eckpaar finden müssen v, V ' in der Grafik.

Diese Verallgemeinerungen weisen signifikant effizientere Algorithmen auf als der vereinfachte Ansatz, einen einzelpaarkürzesten Pfadalgorithmus auf allen relevanten Scheitelpunkten auszuführen.

Algorithmen

Die wichtigsten Algorithmen zur Lösung dieses Problems sind:

Dijkstra -Algorithmus Löst das kürzeste Pfadproblem mit dem nicht negativen Randgewicht.
Bellman -.ford -Algorithmus Löst das Problem mit einer Source, wenn die Kantengewichte negativ sein können.
Ein* Suchalgorithmus Löst für den kürzesten einzelnen Pair-Pfad mitheuristik, um zu versuchen, die Suche zu beschleunigen.
Floyd -Warshall -Algorithmus Löst alle Paare kürzeste Wege.
Johnsons Algorithmus Löst alle Paare am kürzesten We spärliche Grafiken.
Viterbi -Algorithmus Löst das kürzeste stochastische Pfadproblem mit einem zusätzlichen probabilistischen Gewicht auf jedem Knoten.

Zusätzliche Algorithmen und zugehörige Bewertungen können in gefunden werden Cherkassky, Goldberg & Radzik (1996).

Kürzeste Wege mit Single-Source

Ungerichtete Grafiken

Gewichte	Zeitkomplexität	Autor
${\ displaystyle \ mathbb {r}}$ ₊	O(V²)	Dijkstra 1959
${\ displaystyle \ mathbb {r}}$ ₊	O((E+V) ProtokollV)	Johnson 1977 (Binärhaufen))
${\ displaystyle \ mathbb {r}}$ ₊	O(E+VProtokollV)	Fredman & Tarjan 1984 (Fibonacci Heap))
${\ displaystyle \ mathbb {n}}$	O(E)	Thorup 1999 (erfordert eine Multiplikation mit konstanter Zeit)

Ungewichtete Grafiken

Algorithmus	Zeitkomplexität	Autor
Breite-First-Suche	O(E+V)

Gerichtete acyclische Graphen (DAGs)

Ein Algorithmus verwendet Topologische Sortierung kann das kürzeste einkürzeste Wegproblem rechtzeitig lösen $Θ (E + V)$ in willkürlich gewichteten DAGs.^[1]

Gerichtete Grafiken mit nichtnegativen Gewichten

Die folgende Tabelle wird von entnommen Schrijver (2004), mit einigen Korrekturen und Ergänzungen. Ein grüner Hintergrund zeigt eine asymptotisch am besten gebundene in der Tabelle an; L ist die maximale Länge (oder das Gewicht) zwischen allen Kanten unter der Annahme von Ganzzahlkantengewichten.

Gewichte	Algorithmus	Zeitkomplexität	Autor
${\ displaystyle \ mathbb {r}}$		${\ displayStyle o (v^{2} el)}$	Ford 1956
${\ displaystyle \ mathbb {r}}$	Bellman -.ford -Algorithmus	${\ displayStyle o (ve)}}$	Shimbel 1955, Bellman 1958, Moore 1959
${\ displaystyle \ mathbb {r}}$		${\ displayStyle o (v^{2} \ log {v})}$	Dantzig 1960
${\ displaystyle \ mathbb {r}}$	Dijkstra -Algorithmus mit Liste	${\ displayStyle o (v^{2})}$	Leyzorek et al. 1957, Dijkstra 1959, Minty (siehe Pollack & Wiebenson 1960), Whiting & Hillier 1960
${\ displaystyle \ mathbb {r}}$	Dijkstra -Algorithmus mit Binärhaufen	${\ displayStyle o ((e+v) \ log {v})}$	Johnson 1977
${\ displaystyle \ mathbb {r}}$	Dijkstra -Algorithmus mit Fibonacci Heap	${\ displayStyle o (e+v \ log {v})}$	Fredman & Tarjan 1984, Fredman & Tarjan 1987
${\ displaystyle \ mathbb {n}}$	Dial's Algorithmus^[2] (Dijkstra -Algorithmus Verwendung einer Eimer -Warteschlange mit L Eimer)	${\ displayStyle o (e+lv)}}$	Zifferblatt 1969
		${\ displayStyle o (e \ log {\ log {l}})}$	Johnson 1981, Karlsson & Poblete 1983
	Gabows Algorithmus	${\ displayStyle o (e \ log _ {e/v} l)}$	Gabow 1983, Gabow 1985
		${\ displayStyle o (e+v {\ sqrt {\ log {l}}})}$	Ahuja et al. 1990
	Thorup	${\ displayStyle o (e+v \ log {\ log {v}})}$	Thorup 2004

Gerichtete Grafiken mit willkürlichen Gewichten ohne negative Zyklen

Gewichte	Algorithmus	Zeitkomplexität	Autor
${\ displaystyle \ mathbb {r}}$		O(V²El)	Ford 1956
${\ displaystyle \ mathbb {r}}$	Bellman -.ford -Algorithmus	O(Ve)	Shimbel 1955, Bellman 1958, Moore 1959
${\ displaystyle \ mathbb {r}}$	Johnson-Dijkstra mit Binärhaufen	O(V(E+LogV))	Johnson 1977
${\ displaystyle \ mathbb {r}}$	Johnson-Dijkstra mit Fibonacci Heap	O(V(E+LogV))	Fredman & Tarjan 1984, Fredman & Tarjan 1987, adaptiert nach Johnson 1977
${\ displaystyle \ mathbb {n}}$	Johnsons Technik angewendet auf den Algorithmus des Dial^[2]	O(V(E+L))	Zifferblatt 1969, adaptiert nach Johnson 1977

Gerichtete Grafiken mit willkürlichen Gewichten mit negativen Zyklen

Findet einen negativen Zyklus oder berechnet Entfernungen für alle Eckpunkte.

Gewichte	Algorithmus	Zeitkomplexität	Autor
${\ displaystyle \ mathbb {z}}$	Andrew V. Goldberg	${\ displayStyle o (e {\ sqrt {v}} \ log {n})}$

Planar gerichtete Diagramme mit willkürlichen Gewichten

All-Pairs kürzeste Wege

Das Problem des kürzesten Weges von All-Pairs findet die kürzesten Wege zwischen jedem Eckpunktpaar $v$ , $V '$ in der Grafik. Das Problem der All-Pairs-kürzesten Pfade für ungewichtete gezielte Diagramme wurde von eingeführt von Shimbel (1953), wer beobachtete, dass es durch eine lineare Anzahl von Matrixmultiplikationen gelöst werden könnte $O (V 4)$ .

Ungerichtete Grafik

Gewichte	Zeitkomplexität	Algorithmus
${\ displaystyle \ mathbb {r}}$ ₊	$O (V 3)$	Floyd -Warshall -Algorithmus
${\ displayStyle \ {1, \ infty \}}$	${\ displayStyle o (v^{\ Omega} \ log v)}$	Seidels Algorithmus (erwartete Laufzeit)
${\ displaystyle \ mathbb {n}}$	${\ displayStyle o (v^{3}/2^{\ Omega (\ log n)^{1/2}})}$	Williams 2014
${\ displaystyle \ mathbb {r}}$ ₊	$O (Ev log α (E, V))$	Pettie & Ramachandran 2002
${\ displaystyle \ mathbb {n}}$	$O (Ev)$	Thorup 1999 angewendet auf jeden Scheitelpunkt (erfordert eine Multiplikation mit konstanter Zeit).

Gerichteter Graph

Gewichte	Zeitkomplexität	Algorithmus
${\ displaystyle \ mathbb {r}}$ (Keine negativen Zyklen)	$O (V 3)$	Floyd -Warshall -Algorithmus
${\ displaystyle \ mathbb {n}}$	${\ displayStyle o (v^{3}/2^{\ Omega (\ log n)^{1/2}})}$	Williams 2014
${\ displaystyle \ mathbb {r}}$ (Keine negativen Zyklen)	$O (Ev + V 2 Protokoll V)$	Johnson -Dijkstra
${\ displaystyle \ mathbb {r}}$ (Keine negativen Zyklen)	$O (Ev + V 2 Protokollprotokoll V)$	Pettie 2004
${\ displaystyle \ mathbb {n}}$	$O (Ev + V 2 Protokollprotokoll V)$	Hagerup 2000

Anwendungen

Die kürzesten Pfadalgorithmen werden angewendet, um automatisch Anweisungen zwischen physischen Stellen zu finden, z. B. Anweisungen an der Fahrt Webzuordnung Websites mögen MAPQUEST oder Google Maps. Für diese Anwendung sind schnelle Spezialalgorithmen verfügbar.^[3]

Wenn man ein nicht deterministisches darstellt abstrakte Maschine Als Diagramm, in dem Scheitelpunkte Zustände und Kanten beschreiben, können kürzeste Pfadalgorithmen verwendet werden, um eine optimale Folge von Auswahlmöglichkeiten zu finden, um einen bestimmten Zielzustand zu erreichen, oder um die Zeit, die für die Erreichung eines bestimmten Zustands erforderlich ist, niedrigere Grenzen festzulegen. Zum Beispiel, wenn Scheitelpunkte die Zustände eines Puzzles wie a darstellen Zauberwürfel und jede gerichtete Kante entspricht einer einzelnen Bewegung oder einem einzelnen Drehen, kürzeste Pfadalgorithmen können verwendet werden, um eine Lösung zu finden, die die minimale Anzahl von Bewegungen verwendet.

In einem Networking oder Telekommunikation Denkweise, dieses kürzeste Pfadproblem wird manchmal als Min-Delay-Pfadproblem bezeichnet und normalerweise mit a verbunden größtes Pfadproblem. Zum Beispiel kann der Algorithmus den kürzesten (min-delay) größten oder am weitesten am kürzesten (min-Delay) bewegenden Pfad suchen.

Eine unbeschwertere Anwendung ist die Spiele von "Sechs Grade der Trennung"Sie versuchen, den kürzesten Weg in Grafiken zu finden, wie Filmstars, die im selben Film erscheinen.

Andere Anwendungen, oft untersucht in Unternehmensforschung, enthalten Anlagen- und Anlagenlayout, Robotik, Transport, und VLSI Entwurf.^[4]

Straßennetzwerke

Ein Straßennetz kann als Diagramm mit positiven Gewichten betrachtet werden. Die Knoten repräsentieren Straßenübergänge und jede Kante des Diagramms ist einem Straßensegment zwischen zwei Kreuzungen zugeordnet. Das Gewicht einer Kante kann der Länge des zugehörigen Straßensegments, der Zeit entsprechen, die zum Durchlaufen des Segments erforderlich ist, oder den Kosten für das Durchlaufen des Segments. Mit gerichteten Kanten ist es auch möglich, Einwegstraßen zu modellieren. Solche Grafiken sind in dem Sinne besonders, dass einige Kanten wichtiger sind als andere für Fernreisen (z. B. Autobahnen). Diese Eigenschaft wurde mit dem Begriff der Autobahndimension formalisiert.^[5] Es gibt eine große Anzahl von Algorithmen, die diese Eigenschaft ausnutzen und daher in der Lage sind, den kürzesten Weg schneller zu berechnen, als in allgemeinen Grafiken möglich wäre.

Alle diese Algorithmen funktionieren in zwei Phasen. In der ersten Phase wird der Diagramm vorverarbeitet, ohne den Quell- oder Zielknoten zu kennen. Die zweite Phase ist die Abfragephase. In dieser Phase sind Quell- und Zielknoten bekannt. Die Idee ist, dass das Straßennetz statisch ist, sodass die Vorverarbeitungsphase einmal durchgeführt und für eine große Anzahl von Abfragen im selben Straßennetz verwendet werden kann.

Der Algorithmus mit der am schnellsten bekannten Abfragezeit wird als Hub -Kennzeichnung bezeichnet und kann den kürzesten Weg in den Straßennetzwerken Europas oder den USA in einem Bruchteil einer Mikrosekunde berechnen.^[6] Andere Techniken, die verwendet wurden, sind:

Alt (Eine Suche, Wahrzeichen und Dreiecksungleichung)
Bogenflaggen
Kontraktion hierarchien
Transitknoten -Routing
Reichweite Beschneidung
Beschriftung
Hub -Etiketten

Lineare Programmierformulierung

Es gibt eine natürliche Lineares Programmieren Formulierung für das kürzeste Pfadproblem, unten angegeben. Es ist sehr einfach im Vergleich zu den meisten anderen Verwendungen von linearen Programmen in Diskrete OptimierungEs zeigt jedoch Verbindungen zu anderen Konzepten.

Bei einer gerichteten Grafik (V, A) mit Quellknoten s, Zielknoten tund Kosten w_ij für jede Kante (i, j) in ABetrachten Sie das Programm mit Variablen x_ij

minimieren

{\ displaystyle \ sum _ {ij \ in a} w_ {ij} x_ {ij}}

vorbehaltlich

{\ displayStyle x \ Geq 0}

und für alle i,

oder & {\ text {if}} i = t; \\ 0, & {\ text {sonst.}} \ end {cases}}}

Die Intuition dahinter ist das ${\ displaystyle x_ {ij}}$ ist eine Indikatorvariable dafür, ob Kante (i, j) ist Teil des kürzesten Weges: 1 Wenn es ist, und 0, wenn es nicht ist. Wir möchten den Satz von Kanten mit minimalem Gewicht auswählen, vorbehaltlich der Einschränkung, von der dieser Satz einen Pfad bildet s zu t (dargestellt durch die Gleichstellungsbeschränkung: für alle Scheitelpunkte außer s und t Die Anzahl der eingehenden und ausstehenden Kanten, die Teil des Pfades sind, muss gleich sein (d. H. Es sollte ein Weg von s zu t sein).

Diese LP hat die spezielle Eigenschaft, dass sie integriert ist. genauer gesagt jeder Grundlegende optimale Lösung (wenn man existiert) hat alle Variablen gleich 0 oder 1, und der Satz von Kanten, deren Variablen gleich 1 bilden s-t Dipath. Siehe Ahuja et al.^[13] Für einen Beweis, obwohl der Ursprung dieses Ansatzes bis Mitte des 20. Jahrhunderts zurückreicht.

Das Dual für dieses lineare Programm ist

maximieren y_t − y_s vorbehaltlich für alle ij, y_j − y_i ≤ w_ij

und machbare Duals entsprechen dem Konzept von a konsequent heuristisch für die A* Algorithmus für kürzeste Wege. Für jeden realisierbaren Dual y das reduzierte Kosten ${\ displayStyle w '_ {ij} = w_ {ij} -y_ {j}+y_ {i}}$ sind nicht negativ und EIN* im Wesentlichen läuft Dijkstra -Algorithmus Bei diesen reduzierten Kosten.

Allgemeines algebraisches Rahmen für Semirings: Das algebraische Pfadproblem

Viele Probleme können als Form des kürzesten Weges für einige angemessen ersetzte Additionsvorstellungen entlang eines Pfades und das Minimum eingerahmt werden. Der allgemeine Ansatz für diese besteht darin, die beiden Operationen als die von a zu betrachten Seming. Die Seming -Multiplikation erfolgt entlang des Pfades und der Zugabe zwischen den Pfaden. Dieser allgemeine Rahmen ist als das bekannt Algebraischer Pfadproblem.^[14]^[15]^[16]

Die meisten der klassischen kürzesten Pfadalgorithmen (und neuen) können als Lösen linearer Systeme über solche algebraischen Strukturen formuliert werden.^[17]

In jüngerer Zeit wurde im Rahmen des Banners von ein noch allgemeinerer Rahmen für die Lösung dieser (und viel weniger offensichtlich verwandten Probleme) entwickelt Bewertungsalgebren.^[18]

Kürzester Weg in stochastischen zeitabhängigen Netzwerken

In realen Situationen ist das Transportnetz normalerweise stochastisch und zeitabhängig. Tatsächlich kann ein Reisender, der eine Verbindung täglich durchquert . Infolgedessen ist ein stochastisches zeitabhängiges (STD) -Netzwerk eine realistischere Darstellung eines tatsächlichen Straßennetzes im Vergleich zum deterministischen.^[19]^[20]

Trotz erheblicher Fortschritte im Verlauf des letzten Jahrzehnts bleibt es eine kontroverse Frage, wie ein optimaler Weg in stochastischen Straßennetzwerken definiert und identifiziert werden sollte. Mit anderen Worten, es gibt keine einzigartige Definition eines optimalen Weges unter Unsicherheit. Eine mögliche und häufige Antwort auf diese Frage ist, einen Weg mit der minimalen erwarteten Reisezeit zu finden. Der Hauptvorteil dieses Ansatzes besteht darin, dass effiziente kürzeste Pfadalgorithmen für die deterministischen Netzwerke leicht eingesetzt werden können, um den Pfad mit der minimalen erwarteten Reisezeit in einem stochastischen Netzwerk zu identifizieren. Der resultierende optimale Pfad, der durch diesen Ansatz identifiziert wird, ist jedoch möglicherweise nicht zuverlässig, da dieser Ansatz die Variabilität der Reisezeit nicht angeht. Um dieses Problem anzugehen, verwenden einige Forscher die Verteilung der Reisezeit anstelle des erwarteten Wertes davon, sodass die Wahrscheinlichkeitsverteilung der Gesamtreisezeit mit unterschiedlichen Optimierungsmethoden wie z. Dynamische Programmierung und Dijkstra -Algorithmus .^[21] Diese Methoden verwenden Stochastische Optimierungspezifisch stochastische dynamische Programmierung, um den kürzesten Weg in Netzwerken mit probabilistischer Bogenlänge zu finden.^[22] Das Konzept der Reisezeitzuverlässigkeit wird austauschbar mit der Variabilität der Reisezeit in der Transportforschungsliteratur verwendet, sodass man im Allgemeinen sagen kann, dass die Zuverlässigkeit, je höher die Variabilität der Reisezeit ist, die Zuverlässigkeit sein würde und umgekehrt.

Um die Zuverlässigkeit der Reisezeit genauer zu berücksichtigen, wurden zwei gemeinsame alternative Definitionen für einen optimalen Weg unter Unsicherheit vorgeschlagen. Einige haben das Konzept des zuverlässigsten Pfades eingeführt, um die Wahrscheinlichkeit zu maximieren, dass sie rechtzeitig oder früher als ein bestimmtes Budget der Reisezeit eintreffen. Andere haben alternativ das Konzept eines α-zuverlässigen Pfades vorgestellt, der darauf basiert, dass sie das Reisezeitbudget minimieren wollten, um eine vorgegebene pünktliche Ankunftswahrscheinlichkeit zu gewährleisten.

Siehe auch

Bidirektionale Suche, ein Algorithmus, der den kürzesten Weg zwischen zwei Scheitelpunkten in einem gerichteten Diagramm findet
Euklidischer kürzester Weg
Flussnetzwerk
K kürzester Weg Routing
Min-plus-Matrix-Multiplikation
Wegfindung
Kürzeste Pfadüberbrückung
Kürzester Wegbaum
TRILLER (Transparente Verbindung vieler Links)

Verweise

Anmerkungen

^ Cormen et al. 2001, p. 655
^ ^a ^b Dial, Robert B. (1969). "Algorithmus 360: Kürzester Wald mit topologischer Reihenfolge [h]". Kommunikation der ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
^ Sanders, Peter (23. März 2009). "Schnelle Routenplanung". Google Tech Talk. Archiviert vom Original am 2021-12-11.
^ Chen, Danny Z. (Dezember 1996). "Entwicklung von Algorithmen und Software für geometrische Pfadplanungsprobleme". ACM Computing -Umfragen. 28 (4es). Artikel 18. doi:10.1145/242224.242246. S2CID 11761485.
^ Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Autobahndimension, kürzeste Wege und nachweislich effiziente Algorithmen". ACM-SIAM-Symposium über diskrete Algorithmen, Seiten 782–793, 2010.
^ Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. Research.microsoft.com/pubs/142356/hl-tr.pdf "Ein Hub-basierter Kennzeichnungsalgorithmus für kürzeste Wege auf Straßennetzwerken". Symposium über experimentelle Algorithmen, Seiten 230–241, 2011.
^ Kroger, Martin (2005). "Kürzester multipler getrennter Pfad zur Analyse von Versteißungen in zwei- und dreidimensionalen polymeren Systemen". Computerphysikkommunikation. 168 (3): 209–232. Bibcode:2005cophc.168..209k. doi:10.1016/j.cpc.2005.01.020.
^ Lozano, Leonardo; Medaglia, Andrés L (2013). "Auf einer genauen Methode für das eingeschränkte kürzeste Pfadproblem". Computer & Operations Research. 40 (1): 378-384. doi:10.1016/j.cor.2012.07.008.
^ Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Optimale Lösung von eingeschränkten Problemen mit Pfadplanung mit Graph-Faltungsnetzwerken und optimierter Baumsuche". 2019 IEEE/RSJ Internationale Konferenz über intelligente Roboter und Systeme (IROS): 3519-3525. Arxiv:2108.01036. doi:10.1109/iros40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID 210706773.
^ Bar-Noy, Amotz; Schieber, Baruch (1991). "Das kanadische Reisendeproblem". Verfahren des zweiten jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen: 261–270. Citeseerx 10.1.1.1088.3015.
^ Nikolova, Evdokia; Karger, David R. "Routenplanung unter Unsicherheit: Das kanadische Reisendeproblem" (PDF). Proceedings der 23. Nationalen Konferenz über künstliche Intelligenz (AAAI): 969-974.
^ Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "Algorithmen zur Erkennung von Zyklus". Mathematische Programmierung. 85 (2): 277–311. doi:10.1007/s101070050058. ISSN 1436-4646.
^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Netzwerkströme: Theorie, Algorithmen und Anwendungen. Prentice Hall. ISBN 978-0-13-617549-0.
^ Paar, Claude (1967). "Sur des Algorithmes Pour des Problèmes de Cheminement Dans Les Graphes Finis (auf Algorithmen für Pfadprobleme in endlichen Graphen)". Im Rosentiehl, Pierre (ed.). Théorie des Graphes (Journées Internationales D'Études) - Theorie der Graphs (Internationales Symposium). Rom (Italien), Juli 1966: Dunod (Paris) et Gordon und Breach (New York). p. 271.{{}}: CS1 Wartung: Standort (Link)
^ Derniame, Jean Claude; Paar, Claude (1971). Problèmes de cheminement dans les les graphes (Pfadprobleme in Graphen). Dunod (Paris).
^ Baras, John; Theodorakopoulos, George (4. April 2010). Pfadprobleme in Netzwerken. Morgan & Claypool Publishers. S. 9–. ISBN 978-1-59829-924-3.
^ Gondran, Michel; Minoux, Michel (2008). Diagramme, Dioiden und Halbschalter: neue Modelle und Algorithmen. Springer Science & Business Media. Kapitel 4. ISBN 978-0-387-75450-5.
^ Pouly, Marc; Kohlas, Jürg (2011). Generische Inferenz: Eine einheitliche Theorie für automatisierte Argumentation. John Wiley & Sons. Kapitel 6. Bewertungsalgebren für Pfadprobleme. ISBN 978-1-118-01086-0.
^ Loui, R.P., 1983. Optimale Pfade in Graphen mit stochastischen oder mehrdimensionalen Gewichten. Kommunikation der ACM, 26 (9), S. 670-676.
^ Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Multi-Objektiv-Pfad-Befund in stochastischen zeitabhängigen Straßennetzwerken unter Verwendung eines nicht dominierten Sortierens genetischen Algorithmus". Expertensysteme mit Anwendungen. 42 (12): 5056–5064. doi:10.1016/j.eswa.2015.02.046.
^ Olya, Mohammad Hessam (2014). "Finden Sie den kürzesten Weg in einem kombinierten Exponential - Gamma -Wahrscheinlichkeitsverteilungsbogenlänge". Internationales Journal of Operational Research. 21 (1): 25–37. doi:10.1504/ijor.2014.064020.
^ Olya, Mohammad Hessam (2014). "Anwenden des Algorithmus von Dijkstra für das allgemeine kürzeste Pfadproblem mit normaler Wahrscheinlichkeitsverteilungsbogenlänge". Internationales Journal of Operational Research. 21 (2): 143–154. doi:10.1504/ijor.2014.064541.

Literaturverzeichnis

Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (April 1990). "Schnellere Algorithmen für das kürzeste Pfadproblem" (PDF). Journal of the ACM. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. HDL:1721.1/47994. S2CID 5499589.
Bellman, Richard (1958). "Bei einem Routing -Problem". Vierteljährlich angewandte Mathematik. 16: 87–90. doi:10.1090/QAM/102435. HERR 0102435.
Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Kürzeste Pfade Algorithmen: Theorie und experimentelle Bewertung". Mathematische Programmierung. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610 (95) 00021-6. HERR 1392160.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Kürzeste Wege mit Einzelquellen und alle kürzesten Wege". Einführung in Algorithmen (2. Aufl.). MIT Press und McGraw-Hill. S. 580–642. ISBN 0-262-03293-7.
Dantzig, G. B. (Januar 1960). "Auf der kürzesten Route durch ein Netzwerk". Managementwissenschaft. 6 (2): 187–190. doi:10.1287/mnsc.6.2.187.
Dijkstra, E. W. (1959). "Ein Hinweis zu zwei Problemen im Zusammenhang mit Diagrammen". Numerische Mathematik. 1: 269–271. doi:10.1007/bf01386390. S2CID 123284777.
Ford, L. R. (1956). "Netzwerkfluss Theorie". Rand Corporation. P-923. {{}}: Journal zitieren erfordert |journal= (Hilfe)
Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen. 25. jährliches Symposium für Grundlagen der Informatik. IEEE. S. 338–346. doi:10.1109/sfcs.1984.715934. ISBN 0-8186-0591-x.
Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. S2CID 7904683.
Gabow, H. N. (1983). "Skalierungsalgorithmen für Netzwerkprobleme". Verfahren des 24. jährlichen Symposiums für Fundamente der Informatik (FOCS 1983) (PDF). S. 248–258. doi:10.1109/sfcs.1983.68.
Gabow, Harold N. (1985). "Skalierungsalgorithmen für Netzwerkprobleme". Journal of Computer and System Sciences. 31 (2): 148–168. doi:10.1016/0022-0000 (85) 90039-x. HERR 0828519.
Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P.; Welzl, Emo (Hrsg.). Verbesserte kürzeste Wege auf dem Wort RAM. Proceedings des 27. Internationalen Kolloquiums über Automaten, Sprachen und Programmierung. S. 61–72. ISBN 978-3-540-67715-4.
Johnson, Donald B. (1977). "Effiziente Algorithmen für kürzeste Wege in spärlichen Netzwerken". Journal of the ACM. 24 (1): 1–13. doi:10.1145/321992.321993. S2CID 207678246.
Altıntaş, Gökhan (2020). Genaue Lösungen für kürzeste Pfadprobleme auf der Grundlage mechanischer Analogien: im Zusammenhang mit Labyrinths. Amazon Digital Services LLC. p. 97. ISBN 9798655831896.
Johnson, Donald B. (Dezember 1981). "Eine vorrangige Warteschlange, in der die Initialisierung und Warteschlangenvorgänge dauern $O (Protokollprotokoll D)$ Zeit". Theorie der mathematischen Systeme. 15 (1): 295–309. doi:10.1007/bf01786986. HERR 0683047. S2CID 35703411.
Karlsson, Rolf G.; Poblete, Patricio V. (1983). "Ein $O (m Protokollprotokoll D)$ Algorithmus für kürzeste Wege ". Diskrete angewandte Mathematik. 6 (1): 91–93. doi:10.1016/0166-218x (83) 90104-x. HERR 0700028.
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. (1957). Untersuchung von Modelltechniken - Erster Jahresbericht - 6. Juni 1956 - 1. Juli 1957 - Eine Studie über Modelltechniken für Kommunikationssysteme. Cleveland, Ohio: Case Institute of Technology.
Moore, E. F. (1959). "Der kürzeste Weg durch ein Labyrinth". Proceedings of a International Symposium über die Theorie des Switching (Cambridge, Massachusetts, 2. bis 5. April 1957). Cambridge: Harvard University Press. S. 285–292.
Pettie, Seth; Ramachandran, Vijaya (2002). Berechnung kürzester Wege mit Vergleiche und Ergänzungen. Verfahren des 13. jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen. pp.267–276. ISBN 978-0-89871-513-2.
Pettie, Seth (26. Januar 2004). "Ein neuer Ansatz für alle kürzesten Wege auf realgewichtete Graphen.". Theoretische Informatik. 312 (1): 47–74. doi:10.1016/s0304-3975 (03) 00402-x.
Pollack, Maurice; Wiebenson, Walter (März - April 1960). "Lösung des kürzesten Problems-eine Rezension". Operation. Res. 8 (2): 224–230. doi:10.1287/Opre.8.2.224. Attribute Dijkstra's Algorithmus zu Minty ("Privatkommunikation") auf S. 225.
Schrijver, Alexander (2004). Kombinatorische Optimierung - Polyeder und Effizienz. Algorithmen und Kombinatorik. Vol. 24. Springer. ISBN 978-3-540-20456-5. Hier: Vol.A, Sekte.7.5b, p. 103
Shimbel, Alfonso (1953). "Strukturparameter von Kommunikationsnetzwerken". Bulletin der mathematischen Biophysik. 15 (4): 501–507. doi:10.1007/bf02476438.
Shimbel, A. (1955). Struktur in Kommunikationsnetzen. Verfahren des Symposiums über Informationsnetzwerke. New York, NY: Polytechnische Presse des Polytechnic Institute of Brooklyn. S. 199–203.
Thorup, Mikkel (1999). "Ungelenkte Einzel-Source-kürzeste Wege mit positiven Ganzzahl-Gewichten in der linearen Zeit". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
Thorup, Mikkel (2004). "Ganzzahl vorrangige Warteschlangen mit Abnahme der Taste in konstanter Zeit und das Problem der einzelnen Quellenkürzestes.". Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016/j.jcs.2004.04.003.
Whiting, P. D.; Hillier, J. A. (März - Juni 1960). "Eine Methode, um die kürzeste Route durch ein Straßennetz zu finden". Betriebsforschung vierteljährlich. 11 (1/2): 37–40. doi:10.1057/jors.1960.32.
Williams, Ryan (2014). "Schnellere All-Pairs-kürzeste Pfade durch Schaltkomplexität". Proceedings des 46. jährlichen ACM -Symposiums über die Computertheorie (STOC '14). New York: ACM. S. 664–673. Arxiv:1312.6680. doi:10.1145/2591796.2591811. HERR 3238994.

Weitere Lektüre

Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Volldynamischer Ausgangsgrenze mit einem kürzesten Pfadproblem der Quelle". Proc. 7. Annu. ACM-SIAM-Symp. Diskrete Algorithmen. Atlanta, GA. S. 212–221. Citeseerx 10.1.1.32.9856.
Dreyfus, S. E. (Oktober 1967). Eine Bewertung einiger kürzester Pfadalgorithmen (PDF) (Bericht). Projekt Rand. Luftwaffe der Vereinigten Staaten. RM-5433-PR. Archiviert (PDF) Aus dem Original am 17. November 2015. Dtic ad-661265.

[1] Cormen et al. 2001, p. 655

[dial69-2] Dial, Robert B. (1969). "Algorithmus 360: Kürzester Wald mit topologischer Reihenfolge [h]". Kommunikation der ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.

[3] Sanders, Peter (23. März 2009). "Schnelle Routenplanung". Google Tech Talk. Archiviert vom Original am 2021-12-11.

[4] Chen, Danny Z. (Dezember 1996). "Entwicklung von Algorithmen und Software für geometrische Pfadplanungsprobleme". ACM Computing -Umfragen. 28 (4es). Artikel 18. doi:10.1145/242224.242246. S2CID 11761485.

[5] Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Autobahndimension, kürzeste Wege und nachweislich effiziente Algorithmen". ACM-SIAM-Symposium über diskrete Algorithmen, Seiten 782–793, 2010.

[6] Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. Research.microsoft.com/pubs/142356/hl-tr.pdf "Ein Hub-basierter Kennzeichnungsalgorithmus für kürzeste Wege auf Straßennetzwerken". Symposium über experimentelle Algorithmen, Seiten 230–241, 2011.

[7] Kroger, Martin (2005). "Kürzester multipler getrennter Pfad zur Analyse von Versteißungen in zwei- und dreidimensionalen polymeren Systemen". Computerphysikkommunikation. 168 (3): 209–232. Bibcode:2005cophc.168..209k. doi:10.1016/j.cpc.2005.01.020.

[8] Lozano, Leonardo; Medaglia, Andrés L (2013). "Auf einer genauen Methode für das eingeschränkte kürzeste Pfadproblem". Computer & Operations Research. 40 (1): 378-384. doi:10.1016/j.cor.2012.07.008.

[9] Osanlou, Kevin; Bursuc, Andrei; Guettier, Christophe; Cazenave, Tristan; Jacopin, Eric (2019). "Optimale Lösung von eingeschränkten Problemen mit Pfadplanung mit Graph-Faltungsnetzwerken und optimierter Baumsuche". 2019 IEEE/RSJ Internationale Konferenz über intelligente Roboter und Systeme (IROS): 3519-3525. Arxiv:2108.01036. doi:10.1109/iros40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID 210706773.

[10] Bar-Noy, Amotz; Schieber, Baruch (1991). "Das kanadische Reisendeproblem". Verfahren des zweiten jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen: 261–270. Citeseerx 10.1.1.1088.3015.

[11] Nikolova, Evdokia; Karger, David R. "Routenplanung unter Unsicherheit: Das kanadische Reisendeproblem" (PDF). Proceedings der 23. Nationalen Konferenz über künstliche Intelligenz (AAAI): 969-974.

[12] Cherkassky, Boris V.; Goldberg, Andrew V. (1999-06-01). "Algorithmen zur Erkennung von Zyklus". Mathematische Programmierung. 85 (2): 277–311. doi:10.1007/s101070050058. ISSN 1436-4646.

[13] Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Netzwerkströme: Theorie, Algorithmen und Anwendungen. Prentice Hall. ISBN 978-0-13-617549-0.

[Pair1966-14] Paar, Claude (1967). "Sur des Algorithmes Pour des Problèmes de Cheminement Dans Les Graphes Finis (auf Algorithmen für Pfadprobleme in endlichen Graphen)". Im Rosentiehl, Pierre (ed.). Théorie des Graphes (Journées Internationales D'Études) - Theorie der Graphs (Internationales Symposium). Rom (Italien), Juli 1966: Dunod (Paris) et Gordon und Breach (New York). p. 271.{{}}: CS1 Wartung: Standort (Link)

[15] Derniame, Jean Claude; Paar, Claude (1971). Problèmes de cheminement dans les les graphes (Pfadprobleme in Graphen). Dunod (Paris).

[BarasTheodorakopoulos2010-16] Baras, John; Theodorakopoulos, George (4. April 2010). Pfadprobleme in Netzwerken. Morgan & Claypool Publishers. S. 9–. ISBN 978-1-59829-924-3.

[GondranMinoux2008-17] Gondran, Michel; Minoux, Michel (2008). Diagramme, Dioiden und Halbschalter: neue Modelle und Algorithmen. Springer Science & Business Media. Kapitel 4. ISBN 978-0-387-75450-5.

[PoulyKohlas2012-18] Pouly, Marc; Kohlas, Jürg (2011). Generische Inferenz: Eine einheitliche Theorie für automatisierte Argumentation. John Wiley & Sons. Kapitel 6. Bewertungsalgebren für Pfadprobleme. ISBN 978-1-118-01086-0.

[19] Loui, R.P., 1983. Optimale Pfade in Graphen mit stochastischen oder mehrdimensionalen Gewichten. Kommunikation der ACM, 26 (9), S. 670-676.

[20] Rajabi-Bahaabadi, Mojtaba; Shariat-Mohaymany, Afshin; Babaei, Mohsen; Ahn, Chang Wook (2015). "Multi-Objektiv-Pfad-Befund in stochastischen zeitabhängigen Straßennetzwerken unter Verwendung eines nicht dominierten Sortierens genetischen Algorithmus". Expertensysteme mit Anwendungen. 42 (12): 5056–5064. doi:10.1016/j.eswa.2015.02.046.

[21] Olya, Mohammad Hessam (2014). "Finden Sie den kürzesten Weg in einem kombinierten Exponential - Gamma -Wahrscheinlichkeitsverteilungsbogenlänge". Internationales Journal of Operational Research. 21 (1): 25–37. doi:10.1504/ijor.2014.064020.

[22] Olya, Mohammad Hessam (2014). "Anwenden des Algorithmus von Dijkstra für das allgemeine kürzeste Pfadproblem mit normaler Wahrscheinlichkeitsverteilungsbogenlänge". Internationales 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]

[18]

[19]

[20]

[21]

[22]