Der "schnellste kürzeste Pfadalgorithmus" hängt stark von den spezifischen Eigenschaften Ihres Diagramms ab:

1. Art der Grafik:

* gewichtet gegen ungewichtete: Sind die Kanten Ihres Diagramms mit Kosten oder Entfernung (gewichtet) verbunden oder werden alle Kanten als die gleichen Kosten (ungewichtet) angesehen?

* gerichtet gegen nicht gerichtet: Sind die Kanten Richtungsstraßen (Einbahnstraßen) oder bidirektional (Zweiwege-Straßen)?

* cyclisch gegen acyclisch: Enthält der Diagramm Zyklen (Pfade, die zum selben Knoten zurückkehren können)?

* Dichte: Ist die Grafik spärlich (relativ wenige Kanten) oder dicht (viele Kanten)?

* Nicht-negative Gewichte: Sind alle Kantengewichte nicht negativ? Dies ist * entscheidend * für viele Algorithmen, die richtig arbeiten können. Wenn Sie negative Gewichte haben, ist eine spezielle Handhabung erforderlich.

* euclidan gegen nichteuklidan: Können Sie geometrische Eigenschaften verwenden, um Abstände zwischen den Punkten zu schließen?

2. Ziel des Algorithmus:

* kürzester Ein-Source-Pfad: Finden Sie den kürzesten Pfad von einem bestimmten Startknoten zu allen anderen Knoten im Diagramm.

* Einer-Destination kürzester Weg: Finden Sie den kürzesten Pfad von allen Knoten zu einem bestimmten Zielknoten (konzeptionell gleich wie Einzelqualze, wenn Sie die Richtung der Kanten umkehren).

* All-Pairs Kürzester Pfad: Finden Sie den kürzesten Weg zwischen * jedem * Knotenpaar in der Grafik.

* Heuristik erlaubt? Wenn Sie mit einer Annäherung einverstanden sind und den * absoluten * kürzesten Weg nicht garantiert haben, können Sie mit heuristischer Suche oft viel schnellere Ergebnisse erzielen.

Hier ist eine Aufschlüsselung gemeinsamer Algorithmen und ihre typischen Anwendungsfälle:

für ungewichtete Graphen:

* Breite-First-Suche (BFS): Dies ist der * schnellste * und einfachste Algorithmus für ungewichtete Graphen. Es garantiert, dass das kürzeste Weg (in Bezug auf die * Nummer * der Kanten) von einem Quellknoten zu allen anderen erreichbaren Knoten findet.

* Zeitkomplexität: O (v + e) ​​wobei V die Anzahl der Eckpunkte und E ist die Anzahl der Kanten.

für gewichtete Graphen mit nicht negativen Gewichten:

* Dijkstra -Algorithmus: Einer der am häufigsten verwendeten Algorithmen, um den kürzesten Weg von einer einzelnen Quelle zu allen anderen Knoten in einem gewichteten Diagramm mit * nicht negativen * Kantengewichten zu finden.

* Zeitkomplexität:

* O (v^2) (mit einem einfachen Array oder einer Listenimplementierung für die Prioritätswarteschlange)

* O (E + V log v) (mit einem binären Heap oder einer Prioritätswarteschlange)

* O (E + V log* V) (mit Fibonacci -Haufen - in der Praxis aufgrund von Overheads weniger häufig)

* a* Suche: Eine Erweiterung des Algorithmus von Dijkstra, der eine * heuristische * Funktion verwendet, um die Suche zu leiten. Es ist oft deutlich schneller als Dijkstra, wenn Sie gute heuristische Informationen über die verbleibende Entfernung zum Ziel haben.

* Zeitkomplexität: Hängt von der Heuristik ab. Im besten Fall (perfekte Heuristik) kann es sehr schnell sein. Im schlimmsten Fall (schlechte Heuristik) kann es so langsam sein wie Dijkstra.

* a* erfordert eine Heuristik, die zulässig ist (überschätzt niemals die Kosten, um das Ziel zu erreichen) und konsistent (monotonisch).

für gewichtete Graphen mit negativen Gewichten (und ohne negative Zyklen):

* Bellman-Ford-Algorithmus: Kann Grafiken mit negativen Kantengewichten verarbeiten, solange es keine negativen Zyklen gibt (Zyklen, in denen die Summe der Kantengewichte negativ ist). Wenn ein negativer Zyklus vorhanden ist, kann er ihn erkennen.

* Zeitkomplexität: O (v * e)

für All-Pairs-kürzeste Wege:

* Floyd-warshall-Algorithmus: Findet den kürzesten Weg zwischen * jedem * Paar von Scheitelpunkten in einem gerichteten oder ungerichteten Diagramm. Es kann auch negative Kantengewichte (aber keine negativen Zyklen) bewältigen.

* Zeitkomplexität: O (v^3)

* Johnsons Algorithmus: Kann auch All-Pairs-kürzeste Wege finden und negative Kantengewichte bewältigen. Es ist im Allgemeinen schneller als Floyd-Warshall in * spärlichen * Graphen. Es funktioniert durch Neugewicht der Kanten, um negative Gewichte (unter Verwendung von Bellman-Ford) zu beseitigen und dann den Algorithmus von Dijkstra von jedem Scheitelpunkt auszuführen.

* Zeitkomplexität: O (V^2 log v + ve)

Zusammenfassungstabelle

| Algorithmus | Graphentyp | Kantengewichte | Zeitkomplexität | Notizen |

| ------------------ | ---------------------------------------------- | ------------ | -------------------------- | ----------------------------------------------------------- |

| BFS | Ungewichtete | Keine | O (V + E) | Am schnellsten für ungewichtete Graphen. |

| Dijkstra's | Gewichtet, nicht negativ | Nicht negativ | O (E + V log v) | Gemeinsam, funktioniert gut mit der vorrangigen Warteschlange. |

| A* | Gewichtet, nicht negativ | Nicht negativ | Heuristische abhängige | Kann viel schneller sein als Dijkstra, wenn eine gute Heuristik existiert. |

| Bellman-Ford | Gewichtet, kann negative Kanten haben | Any | O (v * e) | Kann negative Zyklen erkennen. |

| Floyd-Warshall | Gewichtet, kann negative Kanten haben (keine Zyklen) | Any | O (v^3) | All-Pairs-kürzeste Wege, gut für dichte Grafiken. |

| Johnson's | Gewichtet, kann negative Kanten haben (keine Zyklen) | Any | O (V^2 log v + ve) | All-pair-kürzeste Wege, besser als Floyd-Warshall für spärliche Graphen |

Praktische Überlegungen und Optimierungen:

* Datenstrukturen: Die Auswahl der Datenstruktur für die Prioritätswarteschlange im Dijkstra -Algorithmus (z. B. binärer Haufen, Fibonacci -Heap) kann die Leistung erheblich beeinflussen, insbesondere für große Graphen.

* Heuristik für a*: Eine gute Heuristik für A* zu wählen ist entscheidend. Eine gut ausgewählte Heuristik kann die Suche drastisch beschleunigen. Gemeinsame Heuristiken sind die euklidische Entfernung (für in einer Ebene eingebettete Grafiken) und die Entfernung von Manhattan.

* Graph -Darstellung: Die Art und Weise, wie Sie Ihr Diagramm darstellen (z. B. Adjazenzliste, Adjazenzmatrix), kann auch die Leistung beeinflussen. Adjazenzlisten werden im Allgemeinen für spärliche Diagramme bevorzugt, während Adjazenzmatrizen für dichte Graphen effizienter sein können.

* Vorverarbeitung: Für wiederholte Grafiken, die wiederholt abgefragt werden, können Sie bestimmte Informationen (z. B. Wahrzeichen, kürzeste Pfadbäume) vorkomputieren, um nachfolgende Abfragen zu beschleunigen.

* reale Straßennetzwerke: Für Straßennetzwerke bieten spezielle Algorithmen wie Kontraktion Hierarchien (CH) und anpassbare Routenplanung (CRP) * viel * schnellere Abfrageszeiten als generische Algorithmen wie Dijkstra, aber sie erfordern eine erhebliche Vorverarbeitung. Diese werden häufig in GPS -Navigationssystemen verwendet.

* Bibliotheken: Verwenden Sie optimierte Bibliotheken (z. B. Networkx in Python, JGRAPHT in Java), wann immer möglich. Diese Bibliotheken bieten häufig hoch optimierte Implementierungen von kürzesten Pfadalgorithmen.

Zusammenfassend, um den "schnellsten" Algorithmus für Ihre Situation zu bestimmen:

1. charakterisieren Sie Ihr Diagramm: Ist es gewichtet, ungewichtet, gerichtet, spärlich, dicht usw.?

2.

3.. sind negative Kantengewichte vorhanden? Wenn ja, sind Sie auf Bellman-Ford (Single-Source) oder Johnson's/Floyd-Warshall (All-Pairs) beschränkt.

4. Wenn nicht negative Gewichte, betrachten Sie Dijkstra oder a*. Wenn ein*, können Sie eine gute Heuristik entwickeln?

5. Für ungewichtete Graphen ist BFS fast immer die beste Wahl.

6. Profil und Benchmark: Experimentieren Sie mit verschiedenen Algorithmen und Datenstrukturen, um festzustellen, welche am besten in Ihrem spezifischen Datensatz und Ihrer Hardware ausgeführt werden.

Wählen Sie den einfachsten Algorithmus, der Ihren Anforderungen entspricht. Verwenden Sie Floyd-Warshall nicht, wenn Sie nur die kürzesten einköpfigen Wege benötigen.