39
menjadi
permanent.
Sekarang
hanya
ada
node
5
yang
masih
temporary, dan statusnya diubah menjadi permanent. Selesai.
Pseudocode untuk algoritma Dijkstra (Horowitz, 1998, p244) adalah
sebagai berikut :
1
DijkstraShortestPaths(int v, float const[][SIZE],
2
float dist[], int n)
3
// dist[j], 1<=j<=n is set to the length of the
4
// shortest path from vertex v to vertex j in a
5
// digraph G with n vertices. dist[v] is set to
6
// zero. G is represented by its cost adjacency
7
// matrix cost[1:n][1:n]
8
{
9
int u; bool S[SIZE];
10
for (int i=1; i<=n; i++) { // Initialize S.
11
S[i] = false; dist[i] = cost[v][i];
12
}
13
S[v] = true; dist[v] = 0.0; // Put v in S.
14
for (int num = 2; num < n; num++ ){
15
// Determine n-1 paths from v.
16
choose u from among those vertices not
17
in S such that dist[u] us minimum;
18
S[u] = true; // Put v in S.
19
for (int w=1; w<=n; w++) // Update distances.
20
if ((S[q]==false && (dist[w]>dist[u]+cost[u][w]))
21
dist[w] = dist[u] + cost[u][w];
22
}
23
}
 |