In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?

Antwort: B. S→B→A→C→T, Länge 7

Der Dijkstra-Algorithmus legt wiederholt den nächstgelegenen Knoten, dessen Entfernung noch nicht feststeht, endgültig fest und aktualisiert die Entfernungen seiner Nachbarn. Ausgehend von S (0) wird B mit 1 festgelegt; über B erhält A die Entfernung 1 + 2 = 3, kürzer als die direkten 4. Mit der Festlegung von A (3) erhalten C den Wert 3 + 1 = 4 und T den Wert 3 + 6 = 9, und die Festlegung von C (4) aktualisiert T auf 4 + 3 = 7. Der kürzeste Weg ist daher S→B→A→C→T mit der Länge 7. S→A→C→T (8) ist länger, weil er S−A direkt nimmt, und S→B→C→T (9) ist länger, weil B−C das große Gewicht 5 hat.