40
terpendek
menuju verteks tersebut. Jika
v
termasuk F,
maka
untuk sejauh
ini
d[v]
masih
merupakan jarak
terpendek
(
masih
bisa
berubah).
Selain
itu, jika v tidak termasuk S maupun F maka d[v] belum bernilai.
Di
bawah
ini
diberikan pseudocode dari
algoritma
Dijkstra.
L(u,
v) adalah panjang edge dari u ke v.
Procedure Dijkstra :
S = {s};
F = OUT(s);
For v in OUT(s) {d[v] = length (s,v);}
While F is not empty {
V = u such that d[u] is minimum among u in F;
F = F – {v};
S = S + {v};
For w in OUT(v) {
If w is not in S {
New_dist = d[v] + L(v,w);
If w is in F {d[w] = min (d[w], New_dist);}
Else {
D[w] = New_dist;
F = F + {w};
}
}
}
}
 |