Page 1 of 1
6. Suppose Dijkstra's algorithm is run on the following graph, starting at node A, (a) Draw one or multiple table showin
Posted: Mon Jun 06, 2022 6:52 pm
by 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 35 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.