Bellman-Ford/Floyed-Warshall

null
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 168
Registriert: 21. Apr 2012 14:58

Bellman-Ford/Floyed-Warshall

Beitrag von null »

Hallo zusammen,

ich habe zwei Fragen an die Community:

1.) Beim Diskstra-Algorithmus ist der Weg bei der i-ten Iteration bis zu diesem Punkt am kürzesten. Herr Weihe hat dies immer mit dem grünen Bereich dargestellt. Ist meine Annahme richtig, dass dies jedoch bei den beiden anderen Algorithmen nicht der Fall ist? Kann man da überhaupt noch von einem grünen und roten Bereich sprechen?

2.) Verstehe ich das richtig, dass beim Bellman-Ford-Algorithmus bei jedem Schritt, jeder Knoten u in den bisherigen Pfad eingefügt wird und so der kürzeste, eventuell neue Pfad gesucht wird? Das ist doch unglaublich aufwendig und wenn ich mir das Beispiel Frankfurt-Kapstadt anschaue, dann verstehe ich nicht, wie solch eine Berechnung läuft. Wir also bei jedem neuen Schritt, jeder Knoten betrachtet (in der Wiki also u) bezeichnet? Ein Navi kann doch gar nicht auf dieser Basis arbeiten...

Vielen Dank

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Bellman-Ford/Floyed-Warshall

Beitrag von Prof. Karsten Weihe »

null hat geschrieben: Beim Diskstra-Algorithmus
Dijkstra :!: :evil: :roll: :wink:
null hat geschrieben: ist der Weg bei der i-ten Iteration bis zu diesem Punkt am kürzesten. Herr Weihe hat dies immer mit dem grünen Bereich dargestellt.
Was ich mit dem grünen Bereich dargestellt habe, ist die Menge aller Knoten, die schon endgültig behandelt wurden, und deren Distanzwert garantiert schon korrekt ist.

null hat geschrieben: Ist meine Annahme richtig, dass dies jedoch bei den beiden anderen Algorithmen nicht der Fall ist? Kann man da überhaupt noch von einem grünen und roten Bereich sprechen?
Nein, kann man nicht und habe ich auch nicht. :wink:

Vielleicht folgende Hintergrundinfo: In der Literatur unterscheidet man zwischen label-setting und label-correcting Algorithmen. Dijkstra gehört zur ersten, die anderen beiden zur zweiten Klasse. Grob gesprochen heißt label-setting, dass der Distanzwert eines Knotens irgendwann mittendrin fertig ist, während man bei label-correcting Algorithmen erst ganz am Ende korrekte Distanzwerte aller Knoten garantieren kann.

null hat geschrieben: Verstehe ich das richtig, dass beim Bellman-Ford-Algorithmus bei jedem Schritt, jeder Knoten u in den bisherigen Pfad eingefügt wird und so der kürzeste, eventuell neue Pfad gesucht wird?
Nein, für jeden Knoten \(u\) wird geschaut, wie lang der Pfad von \(v\) nach \(w\) ist, der aus dem bisher kürzesten Weg von \(v\) nach \(u\) plus der Kante von \(u\) nach \(w\) besteht. Der kürzeste von allen diesen Pfaden wird mit dem bisherigen \((v,w)\)-Pfad verglichen, und der kürzere von diesen beiden ist der neue \((v,w)\)-Pfad.

Ich habe im vorhergehenden Absatz nichts anderes gemacht, als die Formel zu paraphrasieren :!: :roll: :cry:
null hat geschrieben:Ein Navi kann doch gar nicht auf dieser Basis arbeiten...
Navis arbeiten auf der Basis von Dijkstra, nicht von Bellman-Ford. Man will ja mit dem Navi kein All-Pairs Problem lösen. :wink:

KW

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Bellman-Ford/Floyed-Warshall

Beitrag von sab »

Ich habe noch eine Frage zur Minimumsfunktion in Bellman-Ford:
Im Wiki heißt es:
\(M(v,w):=\min\left\{M(v,w),\,\min\{M(v,u)+\ell(u,w)\,|\,u\in V\setminus\{v,w\}\}\right\}\)
Die zweite innere Minimumsfunktion bildet doch kein Minimum, oder? Eine Minimumsfunktion min(x,y) gibt den kleineren Wert zurück. Wenn ich das richtig betrachte, habe ich aber min(x, min(\(y_1\) + \(y_2\))) = min(x, min(y)). Bilde ich hier aufgrund der Addition kein Minimum oder stehe ich nur auf dem Schlauch?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Bellman-Ford/Floyed-Warshall

Beitrag von Prof. Karsten Weihe »

sab hat geschrieben: \(M(v,w):=\min\left\{M(v,w),\,\min\{M(v,u)+\ell(u,w)\,|\,u\in V\setminus\{v,w\}\}\right\}\)
Die zweite innere Minimumsfunktion bildet doch kein Minimum, oder? Eine Minimumsfunktion min(x,y) gibt den kleineren Wert zurück.
Das zweite "min" bildet nicht das Minimum über zwei Werte, sondern das Minimum über eine Menge, nämlich über \(V\setminus\{v,w\}\).

KW

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Bellman-Ford/Floyed-Warshall

Beitrag von sab »

Prof. Karsten Weihe hat geschrieben: Das zweite "min" bildet nicht das Minimum über zwei Werte, sondern das Minimum über eine Menge, nämlich über \(V\setminus\{v,w\}\).
Ich wusste gar nicht, dass das geht, danke für die Erklärung. Ich hatte das als explizite Bedingung gelesen, also das \(V\setminus\{v,w\}\).
Wenn ich \(M(v,w):=\min\left\{M(v,w),\,\min\{M(v,u)+\ell(u,w)\,|\,u\in V\setminus\{v,w\}\}\right\}\) nochmal in Worte fasse:

Ich bilde das Minimum aus (1) meinem aktuellen Pfad von v nach w und (2) dem neuen Teilpfad von v nach u und u nach w, wobei (u,w) in der Menge der Knoten liegen muss?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Bellman-Ford/Floyed-Warshall

Beitrag von Prof. Karsten Weihe »

sab hat geschrieben:
Prof. Karsten Weihe hat geschrieben: Das zweite "min" bildet nicht das Minimum über zwei Werte, sondern das Minimum über eine Menge, nämlich über \(V\setminus\{v,w\}\).
Ich wusste gar nicht, dass das geht, danke für die Erklärung.
In punkto Notation geht alles, was man will (gilt natürlich nicht für Kontexte, in denen vorher vereinbarte gemeinsame Notation essentiell ist, bspw. Klausur). :wink:

In der Mathematik ist es absolut gängig, bspw Summe, Produkt, Minimum und Maximum über Mengen zu bilden, also etwa:

\(\sum_{x\in M}f(x)\), \(\prod_{x\in M}f(x)\), \(\min_{x\in M}f(x)\) und \(\max_{x\in M}f(x)\);

oder mit noch anderer Notation, für kompliziertere Fälle, wo es im Subscript eng würde:

\(\sum_{x\in M}\{f(x)\,|\,x\in M\}\), \(\prod_{x\in M}\{f(x)\,|\,x\in M\}\), \(\min_{x\in M}\{f(x)\,|\,x\in M\}\) und \(\max_{x\in M}\{f(x)\,|\,x\in M\}\).

KW

Antworten

Zurück zu „Archiv“