FORD-Algorithmus - für Netzwerke

Sigi
Kann Dir ÜA 3.5 empfehlen (nimmt Bezug auf ÜA 3.4).
Hier wird der Ford-Algorithums auch gut vom Dijkstra-Algorithmus abgegrenzt.

Wichtig: Ford kann man für beliebige Netzwerke,Dijkstra nur für nichtnegative Netzwerke einsetzen.
Bei Bellmann dürfen keine Zyklen auftreten(negative Bewertungen aber ok).

William,

danke für den Tipp.

Mal eine Frage, ich mache gerade die Übung 3.4. - und dachte hätte den Dijstras-Algorithmus verstanden (bis jetzt).


Der 1. Iteration ist mir klar.
Bei der 2. Iteration nehme ich mir einen Knoten den ich markiert habe und gehe von diesem weiter - in der Übund Knoten D. Nehme ich immer den Knoten mit der kleinsten Bewertung/Entfernung (wie in der Übung) oder kann ich irgendeinen wählen (sprich das erste Element in meiner Openliste)?

Was mich aber viel mehr erstaunt ist, daß ich den Knoten D in der 2. Iteration endgültig markiere - ich hätte vielmehr F endgültig markiert. Woher weiß ich außer durch hinschauen ob ein Knoten endgültig markiert werden sollte?

Warum ist das Ergebnis von a) kein Gerüst?

Hi
Man nimmt immer den Knoten mit dem Minimum (siehe auch Algorithmus 3.3.,Schritt 2,erster Punkt).
Zur endgültigen Markierung: den Knoten,der das Minimum hat,markierst Du endgültig.
Man benutzt diesen Knoten,um Verkürzungen zu bekommen und dann wird er ausrangiert.
Warum sollte man F endgültig markieren ohne den Nutzen aus diesem Knoten zu ziehen?
Das Ergebnis in a) ist kein Minimalgerüst(ein Gerüst ist es schon!).
Es gibt halt ein Gerüst,das noch kürzere Kanten hat zusammen genommen(siehe Lösung).