6. Suppose Dijkstra's algorithm is run on the following graph, starting at node A, (a) Draw one or multiple table showin

[answerhappygod]

6 Suppose Dijkstra S Algorithm Is Run On The Following Graph Starting At Node A A Draw One Or Multiple Table Showin 1 (106.77 KiB) Viewed 34 times

6. Suppose Dijkstra's algorithm is run on the following graph, starting at node A, (a) Draw one or multiple table showing the intermediate distance values (dist(v)) of all the nodes at each iteration of the algorithm. (b) Show the final shortest-path tree. (15') 8 A F 2 2 2 C 1 4. 10 2 B D 16 E H 2 procedure dijkstra (G,1,s) Input: Graph G (V, E), directed or undirected; positive edge lengths {le:ee E}; vertex SE V Output: for all u € V: dist (u) = ∞ prev(u) = nil dist(s) = 0 H = makequeue (V) (using dist-values as keys) while H is not empty: u = deletemin(H) for all edges (u, v) E E: if dist(v) > dist(u) +1(u, v): dist (v) dist(u)+1(u, v) prev(v) = u decreasekey(H, v) G 1 | For all vertices u reachable from s, dist (u) is set to the distance from s to u.