Dijkstra's algorithm with heap

Hide text Hide pseudo-code

Apply the following Dijkstra's algorithm that solves the single-source shortest-paths problem starting from node A. Graph G = (V,E,W) is represented as an adjacency list.

Some additional problems.

SSSP-Dijkstra(G,root) // G = (V,E,W)
  1   for each u in V
  2           do u.priority = MAX_VALUE;
  3                u.unvisited = TRUE
  4                u.father = NULL
  5   root.priority = 0 // root in V
  6   Q.Insert(root); // Priority Queue Q
  7   while Q not empty
  8           do u = DeleteMin(Q)
  9                u.unvisited = FALSE
10                add edge (u.father, u) into the spanning tree
11                for each (u,v) in E
12                           do if v.unvisited and u.priority + W(u,v) < v.priority
13                                   then v.father = u
14                                            v.priority = u.priority + W(u,v)
15                                            Q.InsertOrUpdate(v)



  Created Wed Jun 20 16:00:42 EEST 2007 - Powered by SVG-hut