Dijkstra‘s algorithm

Hide text Hide pseudo-code

The task is to solve the single-source shortest-paths problem. The spanning tree is already initialized with the root vertex A, and thus does not containt the edge (A.father, A). Apply the algorithm to the following weighted graph (represented as an adjacency list beside the graphical representation) with the rest of the vertices. In case there exist several items with the same priority, the priority queue behaves like a queue (i.e., the oldest item is removed first).

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 v in V | (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 Fri Oct 30 13:52:50 EET 2009 - Powered by SVG-hut