Dijkstra

Hallo,

ich habe eine Verständnisfrage zum Dijkstra-Algorithmus.
Hier ist ein Pseudocode aus wikipedia:

Funktion Dijkstra(Graph, Startknoten):
       initialisiere(Graph,Startknoten,abstand[],vorgänger[],Q)
       solange Q nicht leer:                       
           u := Knoten in Q mit kleinstem Wert in abstand[]
           entferne u aus Q                               
           für jeden Nachbarn v von u:
               falls v in Q:
                  distanz_update(u,v,abstand[],vorgänger[])   
       return vorgänger[]

.
Hier nun meine Frage: Warum muss der Knoten v, der aktualisiert wird, in Q sein? (Zeile 7). Habe den Code überall in etwa so wie hier gefunden, verstehe aber die Bedeutung der Zeile 7 nicht...ohne müsste der Algorithmus doch eigentlich auch funktionieren.
Hoffe ihr könnt mir vielleicht ein Bsp. geben, wo die Bedeutung der Zeile 7 zum Tragen kommt.
Danke!

MfG
ops

Michael E.

Es funktioniert auch ohne Zeile 7. Denn alle Knoten v, die bereits aus Q rausgeflogen sind, haben einen höchstens so großen Abstand wie u, sodass distanz_update gar nichts macht, weil die Kantengewichte nicht-negativ sind. In der Praxis unterscheidet man aber meist die Knotenzustände Pre-Heap, In-Heap und Post-Heap, um ein bisschen schneller zu werden.

Hallo,
mich hat schon die ganze Zeit gestört, warum die Zeile 7 überall mitimplementiert wurde (man verbraucht ja nur Extra-Code).
Jetzt weiß ich zumindest, dass sie nicht einfach so da steht, sondern schon einen Nutzen hat (auch wenn ich nicht weiß, welchen genau :D)
Vielen Dank für die schnelle Antwort!

MfG
ops

TGGC

Zeile 7 ist prinzipiell dafuer da, das man nicht "zurueck" laeuft (zu Knoten die man schon besucht hat). Damit stellt man auch sicher, das der Algorithmus terminiert, da in jedem Schritt die Menge Q kleiner wird.

Cyres

TGGC schrieb:

Damit stellt man auch sicher, das der Algorithmus terminiert.

Jedenfalls, wenn es keinen negativen Zyklus gibt, aber für negative Kantengewichte ist der Algorithmus eh nicht definiert

Jester

TGGC schrieb:

Zeile 7 ist prinzipiell dafuer da, das man nicht "zurueck" laeuft (zu Knoten die man schon besucht hat). Damit stellt man auch sicher, das der Algorithmus terminiert, da in jedem Schritt die Menge Q kleiner wird.

Die menge Q wird aber in Zeile 5 kleiner, nicht in Zeile 7.

Ich denke eher, dass das ein überbleibsel aus einer implementierung ist, in der Q ne queue war, bei der dann entweder insert oder decreaseKey aufgerufen wurde, je nachdem ob der knoten schon drin ist oder eben nicht.