Ich weiß, wie Dijkstra-Algorithmus funktioniert und dass es in der Zeit O (m + n log n) Zeit ausgeführt werden kann. Woher wissen wir, dass es keinen besseren Algorithmus für single-source kürzeste Pfade als diesen gibt?Woher wissen wir, dass der Dijkstra-Algorithmus der beste Single-Source-Algorithmus für kürzeste Pfade ist?
Der Dijkstra-Algorithmus ist nicht unbedingt der schnellste Algorithmus zum Berechnen der kürzesten Pfade aus einer Quelle in einem Diagramm. Wenn Sie zum Beispiel wissen, dass alle Kanten ganzzahlige Gewichte haben und annehmen, dass ein Maschinenwort groß genug ist, um eine dieser ganzen Zahlen zu enthalten, dann können Sie einen von Thorup entwickelten Algorithmus verwenden, der in der Zeit O (m + n) läuft ist asymptotisch schneller als Dijkstras Algorithmus. Wenn die Kanten ungewichtet sind oder wenn sie alle das gleiche Gewicht haben, dann tut dies ein einfaches BFS in der Zeit O (m + n).
Ist die Frage "woher wissen wir, dass Dijkstra-Algorithmus nicht schneller als das implementiert werden kann?" oder "woher wissen wir, dass dies der schnellstmögliche Single-Source Shortest Paths-Algorithmus für Graphen mit nichtnegativen Kantengewichten ist?" – templatetypedef
Woher wissen wir, dass dies der schnellstmögliche Single-Source-Algorithmus für kürzeste Pfade für Graphen mit nichtnegativen Kantengewichten ist? – AdamSMith