Graphen (Gewichte 3 )

	Die Beobachtungen auf der vorangegangenen Seite zeigen:
das Wesentliche	Man sollte stets den Knoten mit dem kleinsten Wert für dg aus der Datenstruktur entfernen.
	Es resultiert der Algorithmus von Dijkstra (1960), einer der großen Klassiker in der algorithmischen Graphentheorie.
Dijkstra	Algorithmus von Dijkstra Eingabe: Graph G, Knoten v dieses Graphen Ausgabe: gewichteter Abstand dg(w) aller Knoten w von v für alle Knoten w      setze dg(w) = setze dg(v) = 0 füge v in eine (zunächst leere) Datenstruktur D ein solange D nicht leer ist      entnehme einen Knoten w mit minimalem dg(w) aus D      für alle Kanten {w,u}           falls dg(u) =                füge u in D ein           falls dg(u) > dg(w) + g({w,u})                setze dg(u) = dg(w)+g({w,u})
Dijkstra	Hier kannst du den Algorithmus von Dijkstra ausführen. Es gibt wieder zwei interaktive Modi. Im ersten Modus musst du nur jeweils den richtigen Knoten auswählen. Im zweiten Modus musst du auch noch die aktuellen Entfernungen berechnen und eintragen. (Graph 5 ist das Londoner U-Bahn Netz. Suche nun nach der kürzesten Verbindung von v4 zu v21.)
	Und auf dieser  Nebenseite findest du wieder einen formalen Korrektheitsbeweis.

Seite 10/12