Ist der Dijkstra-Algorithmus nur BFS mit einer Prioritätswarteschlange?

21

Laut dieser Seite ist der Dijkstra-Algorithmus nur BFS mit einer Prioritätswarteschlange. Ist es wirklich so einfach? Ich denke nicht.

Barry Fruitman
quelle
1
Warum denkst du das?
Raphael
@Raphael Weil es zu einfach zu sein scheint und es so ist: Ich habe es noch einmal studiert und sehe jetzt, dass es nicht den Abstand zwischen den Knoten verfolgt, also ist es wirklich ein BFS, nicht Dijkstra.
Barry Fruitman
1
Nun, Dijkstra hat die Werte ändern die Warteschlange „sortiert“ mit (oft als „Entspannung“); wenn du das verbietest, ist es nicht dasselbe, stimmt.
Raphael

Antworten:

19

Sie können den Dijkstra-Algorithmus als BFS mit einer Prioritätswarteschlange implementieren (obwohl dies nicht die einzige Implementierung ist).

Der Dijkstra-Algorithmus basiert auf der Eigenschaft, dass der kürzeste Weg von nach t auch der kürzeste Weg zu einem der Scheitelpunkte entlang des Pfades ist. Genau das macht BFS.st

Oder in einer anderen Perspektive: Wie würde sich der Dijkstra-Algorithmus verhalten, wenn alle Gewichte 1 wären? Genau wie BFS.

Shaull
quelle
4

G=(V,E)

Hier ist eine Idee aus dem Buch "Algorithmen (Abschnitt 4.4)" von Dasgupta et al:

e=(u,v)Elele1le1uv

GGG

GG

Gle

Drittens, wie verhält sich der Dijkstra-Algorithmus in ungewichteten Diagrammen?

Es verhält sich genauso wie BFS. Wir arbeiten dies aus zwei Hauptpunkten heraus.

  • Auf "Entspannung".

    Für den Dijkstra-Algorithmus im Allgemeinen ist die Relaxation gewichtet

    for all edges (u,v) in E:
        if dist(v) > dist(u) + w(u,v)
           dist(v) = dist(u) + w(u,v)
    

    dist(v)=w(u,v)=1

    for all edges (u,v) in E:
        if dist(v) = \infty
           dist(v) = dist(u) + 1
    
  • Auf "Prioritätswarteschlange".

    Wenn der Dijkstra-Algorithmus zu einem beliebigen Zeitpunkt in einem ungewichteten Diagramm ausgeführt wird, enthält die Prioritätswarteschlange höchstens zwei unterschiedliche (Entfernungs-) Werte. Daher reicht eine FIFO-Warteschlange von BFS aus.

Hengxin
quelle