Bellman-Ford-Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:05 Mo 09.01.2006 | | Autor: | kuminitu |
Hallo,
habe hier noch eine Frage:
Hier ist eine Version des Bellman-Ford-Algorithmuses:
for(int m=2;m<n;m++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(in tk=0;k<n;k++)
if( u[i][j] > u[i][k] + a[k][j])
u[i][j] = u[i][k] + a[k][j];
tree[i][j]=k;
kann mir jemand erklären was alles bei einer Iteration von m passiert?
ich blick da einfach nicht durch.
MFG
Kuminitu
|
|
| |
|
Hallo kuminitu!
> Hallo,
>
> habe hier noch eine Frage:
> Hier ist eine Version des Bellman-Ford-Algorithmuses:
> for(int m=2;m<n;m++)
> for(int i=0;i<n;i++)
> for(int j=0;j<n;j++)
> for(in tk=0;k<n;k++)
> if( u[j] > u[k] + a[k][j])
> u[j] = u[k] + a[k][j];
>
> tree[j]=k;
> kann mir jemand erklären was alles bei einer Iteration von
> m passiert?
> ich blick da einfach nicht durch.
>
> MFG
> Kuminitu
Ich hatte damals auch meine Probleme mit diesem Algorithmus. Das [mm]m[/mm] bei deiner Version des Algorithmus scheint nichts weiter als ein Schleifenzähler zu sein (kein Index). Dazu zitiere ich mal Till Crueger:
"Vielmehr kann man beweisen, das
nach n-1 Wiederholungen der Schleife ab Zeile 4 alle kürzesten Pfade
gefunden wurden. Damit ist auch klar warum das i nicht innerhalb der
Schleife verwendet wird."
Nur was mich bei "deiner" Version stört, ist die Anzahl der FOR-Schleifen. Vielleicht liegt es ja daran, daß die Version, die wir in der Vorlesung benutzt haben, eine "theoretischere" Darstellung des Algorithmus war, so daß dort weniger Schleifen benötigt wurden. ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Viele Grüße
Karl
|
|
|
| |
|
Hallo und guten Morgen,
es sollte sowas gelten wie: In der m-ten Iteration ist u[i][j] die Laenge eines kuerzesten Pfades mit hoechstens m Kanten von i nach j.
Gruss,
Mathias
|
|
|
|
