A Bit About Dijkstra’s

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.