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.
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)
Start from the line 6 by inserting the source A into the priority queue (in this case it is a binary heap). The heap operations are described below.
Insert new node by drag & dropping a key from the graph into the heap. The priority (distance from the source) is determined automatically. The priority queue maintains the set of shortest-path estimates, and thus those nodes and their dad-links are shaded.
DeleteMin (the smallest key) from the heap by drag & dropping it into the list labeled "Visiting order". The node is marked visited and colored black, which indicates that it belongs to the set S of vertices whose final shortest-path weights from the source have already determined. The path-length is automatically labeled besides the node.
Update a node if relaxation is needed by selecting the node (either from the heap or graph) and pushing the Update button. Again, the priority is determined automatically - at this time through the last node inserted into S. The new node and its dad-link is shaded and the old ones turn blue.
Some additional problems.