prev up inhalt next


6.4 All pairs shortest path

Gesucht: d[i,j] : = Länge des kürzesten Weges von i nach j .

Die Technik zur Berechnung dieser d[i,j] -Werte entspricht der obigen und zwar berechnet man d k[i,j] : = Länge des kürzesten Weges von i nach j , der nur über Knoten {1,...,k} läuft. Initial setzt man d 0[i,j] : = c(i,j) .

Rekursiv bestimmt man nun d k[i,j] : = min {d k - 1[i,j],d k - 1[i,k] + d k - 1[k,j]} . d n[i,j] gibt dann schließlich die Länge des kürzesten Weges von i nach j in G an, der Weg selber ist damit aber noch nicht berechnet! Dies bewerkstelligt man durch fortwährendes

Berechnen einer Matrix w[i,j] :

w[i,j] gibt also den ersten Knoten auf dem (bisher) kürzesten Weg von i nach j an.

Der kürzeste Weg von i nach j ergibt sich also, indem man quasi durch die Matrix w[i,j] ``springt'', also w[...[w[i,j],j]...] berechnet.




prev up inhalt next