Analyse von Graphen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
Ich versuche im Moment den M.B.F.-Algorithmus zu verstehen. Dieser Algorithmus soll einem, von einem bestimmten Startknoten ausgehend, die kürzesten Pfade zu jedem anderen Knoten in einem gerichteten gewichteten Graphen liefern.
Ich habe versucht den Algorithmus(, so wie er im Skript in Pseudo-Code drinsteht, )nachzuvollziehen und scheiterte an einer FOR-Schleife. Bevor ich Details erläutere, will ich noch den Algoritmus aus dem Skript angeben:
[m]\begin{gathered}
1\quad {\text{for }}v \in V - \left\{ {v_1 } \right\}{\text{ do }}l\left( v \right): = \infty ; \hfill \\
2\quad l\left( s \right): = 0; \hfill \\
3\quad {\text{for }}i: = 1{\text{ to }}n - 1{\text{ do}} \hfill \\
4\quad \quad {\text{for }}\left( {v,w} \right) \in E{\text{ do}} \hfill \\
5\quad \quad \quad d: = l\left( v \right) + c\left( {\left( {v,w} \right)} \right); \hfill \\
6\quad \quad \quad {\text{if }}d < l\left( w \right){\text{ then}} \hfill \\
7\quad \quad \quad \quad l\left( w \right): = d;\;p\left( w \right): = v; \hfill \\
\end{gathered}[/m]
So wie ich den Algorithmus verstehe, setzt er erstmal die Entfernungen vom Startknoten zu allen anderen Knoten im Graph auf "unendlich" (also auf 'unerreichbar'), da er ja noch nichts von der Graphenstruktur weiß. Die Entfernung vom Startknoten zu sich selbst ist dann natürlich 0.
(Was jetzt kommt sind meine Vermutungen, da ich den Algorithmus in dieser Form für seltsam halte:)
Danach geht er alle Knoten des Graphen in der FOR-Schleife bei Zeile 3 durch. Existiert von einem solchen Knoten (siehe unten) eine Verbindung zu einem anderen Knoten (siehe unten), so berechnet der Algo die Entfernung zu Diesem, indem er das Gewicht der zugehörigen Kante nimmt und zur Entfernung von $v$ vom Startknoten aus dazuaddiert.
So, das waren meine Vermutungen. Das Problem ist nur, daß die Hauptschleife in Zeile 3 irgendwie keine echten Bezüge zum Schleifenkörper aufweist (wo wird der Index $i$ dann verwendet?) Es ist auch nicht klar, welchen Wert $v$ beim erstmaligen Betreten des Schleifenkörpers hat.
Ausgehend von meinen Vermutungen habe ich nun versucht das Ganze am folgenden Beispiel nachzuvollziehen:
[Dateianhang nicht öffentlich]
[mm]\Large\begin{array}{ccccccccccccccccccc}
v_{1}&v_{2}&v_{3}&v_{4}&v_{5}&v_{6}&v_{7}&v_{8}&v_{9}&v_{10}&v_{11}&v_{12}&v_{13}&v_{14}&v_{15}&v_{16}&v_{17}&v_{18}&v_{19}\\\hline
0&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty&\infty\\\hline
{}&-1&3&8&18&10&3&{}&21&45&28&36&34&19&30&-3&28&37&\textcolor{red}{?}
\end{array}[/mm]
Es ist hier genau das passiert, was ich oben angemerkt habe, der Algorithmus geht munter zur Überprüfung von [mm] $v_8$ [/mm] über, obwohl der Weg vom Startknoten [mm] $v_1$ [/mm] über [mm] $v_{12}$ [/mm] vom Algorithmus noch nicht gefunden worden ist. Die Folge ist nun, daß die Entfernung von [mm] $v_8$ [/mm] zu [mm] $v_1$ [/mm] noch nicht gesetzt wurde, so daß [mm] $v_8 [/mm] = [mm] \infty$ [/mm] gilt. Dadurch wird aber ein kompletter Weg vom Algorithmus nicht weiter betrachtet.
Ich wollte eigentlich nur wissen, was ich hier genau mißverstanden habe und wie ich den obigen Algorithmus zu verstehen habe?
Vielen Dank für eure Mühe!
Viele Grüße
Karl
P.S. Ich habe diese Frage auch ![[]](/images/popup.gif) im Usenet gestellt.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:21 Sa 09.07.2005 | | Autor: | Karl_Pech |
Die Frage wurde von Till Crueger im Usenet beantwortet. Die Diskussion wird dort gegebenenfalls weitergehen.
|
|
|
|
