In der Graph-Theorie ist das kürzeste Pfad-Problem das Problem, einen Pfad zwischen zwei Scheitelpunkten (oder Knoten) in einem solchem Graphen zu finden, dass die Summe der Gewichte seiner konstituierenden Ränder minimiert wird. Ein Beispiel findet die schnellste Weise, von einer Position bis einen anderen auf einer Autokarte zu kommen; in diesem Fall vertreten die Scheitelpunkte Positionen, und die Ränder vertreten Segmente der Straße und werden als erforderlich, beschwert dieses Segment reisen.

Es gibt mehrere Schwankungen gemäß, ob der gegebene Graph ungeleitet, geleitet oder gemischt ist. Für ungeleitete Graphen kann das kürzeste Pfad-Problem wie folgt formell definiert werden. In Anbetracht eines belasteten Graphen (d. h. ein Satz fungieren V von Scheitelpunkten, ein Satz E Ränder und eines reellwertigen Gewichts f: E  R), und Elemente v und v' V, finden einen Pfad P (eine Folge von Rändern) von v bis einen v' V so dass

:ist

unter allen Pfaden minimal, die v zu v in Verbindung stehen'.

Das Problem wird auch manchmal das einzelne Paar kürzestes Pfad-Problem genannt, um es von den folgenden Schwankungen zu unterscheiden:

• Kürzestes Pfad-Problem der einzelnen Quelle, in dem wir kürzeste Pfade von einem Quellscheitelpunkt v zu allen anderen Scheitelpunkten im Graphen finden müssen.
• Kürzestes Pfad-Problem des einzelnen Bestimmungsortes, in dem wir kürzeste Pfade von allen Scheitelpunkten im geleiteten Graphen zu einem einzelnen Bestimmungsort-Scheitelpunkt v finden müssen. Das kann auf die einzelne Quelle kürzestes Pfad-Problem durch das Umkehren der Kreisbogen im geleiteten Graphen reduziert werden.
• Kürzestes Pfad-Problem der Vollpaare, in dem wir kürzeste Pfade zwischen jedem Paar von Scheitelpunkten v, v' im Graphen finden müssen.

Diese Generalisationen haben bedeutsam effizientere Algorithmen als die vereinfachte Annäherung, ein einzelnes Paar kürzester Pfad-Algorithmus auf allen relevanten Paaren von Scheitelpunkten zu führen.

Algorithmen

Die wichtigsten Algorithmen, um dieses Problem zu beheben, sind:

• Der Algorithmus von Dijkstra löst die einzelne Quelle kürzeste Pfad-Probleme.
• Algorithmus von Ford des öffentlichen Ausrufers behebt das Problem der einzelnen Quelle, wenn Rand-Gewichte negativ sein können.
• A* Suchalgorithmus löst für das einzelne Paar kürzesten Pfad mit der Heuristik, um zu versuchen, die Suche zu beschleunigen.
• Algorithmus von Floyd-Warshall löst alle Paare kürzeste Pfade.
• Der Algorithmus von Johnson löst alle Paare kürzeste Pfade und kann schneller sein als Floyd-Warshall auf spärlichen Graphen.
• Unruhe-Theorie findet (schlimmstenfalls) den lokal kürzesten Pfad.

Zusätzliche Algorithmen und vereinigte Einschätzungen können in Cherkassky und al gefunden werden.

Roadnetworks

Ein roadnetwork kann als ein Graph mit positiven Gewichten betrachtet werden. Die Knoten vertreten Straßenverbindungspunkte, und jeder Rand des Graphen wird mit einem Straßensegment zwischen zwei Verbindungspunkten vereinigt. Das Gewicht eines Randes kann der Länge des verbundenen Straßensegmentes entsprechen, die Zeit musste das Segment oder die Kosten überqueren, das Segment zu überqueren. Mit geleiteten Rändern ist es auch zu Mustereinbahnstraßen möglich. Solche Graphen sind im Sinn speziell, dass einige Ränder wichtiger sind als andere für das lange Entfernungsreisen (d. h. Autobahnen). Dieses Eigentum ist mit dem Begriff der Autobahn-Dimension formalisiert worden. (research.microsoft.com/pubs/115272/soda10.pdf) gibt Es eine große Zahl von Algorithmen, die dieses Eigentum ausnutzen und deshalb im Stande sind, den kürzesten viel schnelleren Pfad zu schätzen, als auf allgemeinen Graphen möglich sein würde.

Alle diese Algorithmen arbeiten in zwei Phasen. In der ersten Phase wird der Graph vorbearbeitet, ohne die Quelle oder den Zielknoten zu kennen. Diese Phase kann mehrere Tage für realistische Daten und einige Techniken nehmen. Die zweite Phase ist die Anfragenphase. In dieser Phase sind Quelle und Zielknoten bekannt. Die Laufzeit der zweiten Phase ist allgemein weniger als eine Sekunde. Die Idee besteht darin, dass das Straßennetz statisch ist, so kann die Aufbereitungsphase einmal getan und für eine Vielzahl von Abfragen in demselben Straßennetz verwendet werden.

Der Algorithmus mit der schnellsten bekannten Anfragenzeit wird das Mittelpunkt-Beschriften genannt und ist im Stande, kürzesten Pfad in den Straßennetzen Europas oder der USA in einem Bruchteil einer Mikrosekunde zu schätzen. (research.microsoft.com/pubs/142356/HL-TR.pdf). Andere Techniken, die verwendet worden sind, sind:

• ALT
• Kreisbogen-Fahnen
• Zusammenziehungshierarchien (http://www.springerlink.com/index/j062316602803057.pdf)
• Transitknotenroutenplanung
• Erreichen Sie gestützte Beschneidung
• Das Beschriften

Einzelne Quelle kürzeste Pfade

Geleitete acyclic Graphen

Geleitete Graphen mit nichtnegativen Gewichten

Planare geleitete Graphen mit nichtnegativen Gewichten

Geleitete Graphen mit willkürlichen Gewichten

Planare geleitete Graphen mit willkürlichen Gewichten

Vollpaare kürzeste Pfade

Algorithmus von Floyd-Warshall

Geleitete Graphen mit Einheitsgewichten

Ungeleitete Graphen mit Einheitsgewichten

Geleitete Graphen mit nichtnegativen Gewichten

Planare geleitete Graphen mit nichtnegativen Gewichten

Geleitete Graphen mit willkürlichen Gewichten

Planare geleitete Graphen mit willkürlichen Gewichten

Anwendungen

Kürzeste Pfad-Algorithmen werden angewandt, um Richtungen zwischen physischen Positionen, wie das Fahren von Richtungen auf Webwebsites der kartografisch darstellenden wie Mapquest oder Google Maps automatisch zu finden. Weil sich diese Anwendung schnell spezialisiert hat, sind Algorithmen verfügbar.

Wenn man eine nichtdeterministische abstrakte Maschine als ein Graph vertritt, wo Scheitelpunkte Staaten beschreiben und Ränder mögliche Übergänge beschreiben, können kürzeste Pfad-Algorithmen verwendet werden, um zu finden, dass eine optimale Folge von Wahlen, einen bestimmten Absicht-Staat zu erreichen, oder niedrigere Grenzen auf der Zeit zu gründen, einen gegebenen Staat erreichen musste. Zum Beispiel, wenn Scheitelpunkte die Staaten eines Rätsels wie ein Würfel von Rubik vertreten und jeder geleitete Rand einer einzelnen Bewegung oder Umdrehung entspricht, können kürzeste Pfad-Algorithmen verwendet werden, um eine Lösung zu finden, die die minimale mögliche Zahl von Bewegungen verwendet.

In einem Netzwerkanschluss oder Fernmeldewesen mindset wird dieses kürzeste Pfad-Problem manchmal das Pfad-Problem der Minute-Verzögerung genannt und gewöhnlich mit einem breitesten Pfad-Problem gebunden. Zum Beispiel kann der Algorithmus das kürzeste (Minute-Verzögerung) breitester Pfad, oder am breitesten am kürzesten (Minute-Verzögerung) Pfad suchen.

Eine fröhlichere Anwendung ist die Spiele von "sechs Graden der Trennung", die versuchen, den kürzesten Pfad in Graphen wie Filmstars zu finden, die in demselben Film erscheinen.

Andere Anwendungen schließen "Operationsforschung, Werk und Möglichkeitslay-Out, Robotertechnik, Transport und VLSI Design" ein.

Zusammenhängende Probleme

Für kürzeste Pfad-Probleme in der rechenbetonten Geometrie, sieh Euklidischen kürzesten Pfad.

Das Handlungsreisender-Problem ist das Problem, den kürzesten Pfad zu finden, der jeden Scheitelpunkt genau einmal durchgeht, und zum Anfang zurückkehrt. Verschieden vom kürzesten Pfad-Problem, das in der polynomischen Zeit mit Graphen ohne negative Zyklen gelöst werden kann, ist das Handlungsreisender-Problem NP-complete und, als solcher, wird geglaubt, nicht effizient lösbar zu sein (sieh P = NP Problem). Das Problem, den längsten Pfad in einem Graphen zu finden, ist auch NP-complete.

Das kanadische Reisender-Problem und das stochastische kürzeste Pfad-Problem sind Generalisationen, wo entweder der Graph dem Möbelpacker, Änderungen mit der Zeit nicht völlig bekannt ist, oder wo Handlungen (Traversals) probabilistic sind.

Der kürzeste vielfache getrennte Pfad ist eine Darstellung des primitiven Pfad-Netzes innerhalb des Fachwerks der Theorie von Reptation.

Die Probleme der Wiederberechnung von kürzesten Pfaden entstehen, wenn einige Graph-Transformationen (z.B, Zusammenschrumpfen von Knoten) mit einem Graphen gemacht werden.

Das breiteste Pfad-Problem sucht einen Pfad, so dass das minimale Etikett jedes Randes so groß wie möglich ist.

Geradlinige Programmierformulierung

Es gibt eine natürliche geradlinige Programmierformulierung für das kürzeste Pfad-Problem, das unten gegeben ist. Es ist im Vergleich zum grössten Teil anderen Gebrauches von geradlinigen Programmen in der getrennten Optimierung sehr trivial, jedoch illustriert es Verbindungen zu anderen Konzepten.

In Anbetracht eines geleiteten Graphen (V, A) mit dem Quellknoten s, Zielknoten t und Kosten w für jeden Kreisbogen (ich, j) in A, denken das Programm mit Variablen x

:minimize unterwerfen und für alles ich,

Diese LP, die allgemeines Futter für Operationsforschungskurse ist, hat das spezielle Eigentum, dass es integriert ist; mehr spezifisch hat jede grundlegende optimale Lösung (wenn man besteht) alle Variablen, die 0 oder 1, und der Satz von Rändern gleich sind, deren Variablen gleicher 1 einen s-t dipath bildet. Sieh Ahuja. für einen Beweis, obwohl der Ursprung dieser Annäherung auf die Mitte des 20. Jahrhunderts zurückgeht.

Der Doppel-für dieses geradlinige Programm ist

:maximize y − y unterwerfen für den ganzen ij, y − y ≤ w

und ausführbare duals entsprechen dem Konzept eines konsequenten heuristischen für den A* Algorithmus für kürzeste Pfade. Für jeden ausführbaren Doppely sind die reduzierten Kosten nichtnegativ, und A* führt im Wesentlichen den Algorithmus von Dijkstra auf diesen reduzierten Kosten.

Siehe auch

• Fluss-Netz
• Kürzester Pfad-Baum
• Euklidischer kürzester Pfad
• Minute - plus die Matrixmultiplikation

Weiterführende Literatur