prev up inhalt next


6.1 Algorithmus von Dijkstra

Eine bessere Variante dieses Algorithmus stammt von Dijkstra:


     markiere alle Knoten als vorläufig $\infty$ ;
     markiere den Startknoten (A) als 0; (endgültig)
     REPEAT
          Sei x der zuletzt endgültig markierte Knoten;
          modifiziere alle Nachbarn y von x durch
                    m(y) := min{m(y),m(x)+c(x,y)};
          markiere den Knoten mit der kleinsten vorläufigen
                    Markierung als endgültig;
     UNTIL alle Knoten sind markiert

Die Laufzeit des Dijkstra-Algorithmus liegt in O(|V|2) , was bei dicht besetzten Graphen eine erhebliche Verbesserung des ersten generischen Algorithmus bedeutet.

Allerdings ist auch beim Dijkstra-Algorithmus auf stets positive Kantenkosten zu achten, da der Algorithmus sonst nicht korrekte kürzeste Wege berechnet. Bei negativen Kantenkosten wären nämlich auch negative Zyklen möglich, die die Wohldefiniertheit des kürzesten Wege Problems verletzen würden.


prev up inhalt next