Algorithm
INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v ∈ G.V
2 v.d = ∞
3 v.π = NIL
4 s.d = 0
RELAX(u,v,w)
1 if v.d > u.d + w(u, v)
2 v.d = u.d + w(u,v)
3 v.π = u
DIJKSTRA(G;w;s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S = Ø
3 Q = G.V
4 while Q ≠ Ø
5 u = EXTRACT-MIN(Q)
6 S = S U {u}
7 for each vertex v ∈ G.Adj[u]
8 RELAX(u,v,w)
Pages: Contents … << Previous 4 Next Page>>
One Comment Add yours