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.