1. Directions: Use the following, simple Undirected Graph G = (V, E) shown below for the next subproblems. The following
Posted: Wed Apr 27, 2022 3:36 pm
1. Directions: Use the following, simple Undirected
Graph G = (V, E) shown below for the next
subproblems.
The following Dijkstra's Algorithm shown below serves as
an aid for the next problem.
a.) Fill in the distances and predecessors in the next
tables shown below according to Dijkstra's Algorithm. The rows
correspond to the sequence of steps 0 to 7 as the algorithm
proceeds.
4 d 9 С e 6 8 3 7 Yf 5 a 2 11 09 g 1 b h 10 12
Dmin priority queue starting node > arrays of size n indexed for every v EV Require: Q Require: s Require: dist, P 1: for v #EV do 2: set dist(v):= 3: set p(v):= 0 4: insert (v, dist(v)) into Q 5: set dist(s) := 0 6: set p(s) := 0 7: insert (s, dist(s)) into Q 8: while Q #{} do V + extract-min from Q 10: set v extracted 11: for u € N(v) do 12: if u not extracted then if dist(v) + w(u, v) < dist(u) then 14: set dist(u) := dist(v) + w(u, v) set p(u) := :=V 16: decrease-key for (u, dist(u)) in Q 9: 13: 15:
oo 8 00 8 00 oo 8 DISTANCE a b c d e f g h 00 10 20 30 40 50 60 70 PREDECESSOR a b c d e f g h 0 0 0 0 0 0 0 0 0 10 20 30 4 Ø 50 60 70
Graph G = (V, E) shown below for the next
subproblems.
- 1 Directions Use The Following Simple Undirected Graph G V E Shown Below For The Next Subproblems The Following 1 (59.77 KiB) Viewed 27 times
an aid for the next problem.
- 1 Directions Use The Following Simple Undirected Graph G V E Shown Below For The Next Subproblems The Following 2 (97.95 KiB) Viewed 27 times
tables shown below according to Dijkstra's Algorithm. The rows
correspond to the sequence of steps 0 to 7 as the algorithm
proceeds.
- 1 Directions Use The Following Simple Undirected Graph G V E Shown Below For The Next Subproblems The Following 3 (14.4 KiB) Viewed 27 times
Dmin priority queue starting node > arrays of size n indexed for every v EV Require: Q Require: s Require: dist, P 1: for v #EV do 2: set dist(v):= 3: set p(v):= 0 4: insert (v, dist(v)) into Q 5: set dist(s) := 0 6: set p(s) := 0 7: insert (s, dist(s)) into Q 8: while Q #{} do V + extract-min from Q 10: set v extracted 11: for u € N(v) do 12: if u not extracted then if dist(v) + w(u, v) < dist(u) then 14: set dist(u) := dist(v) + w(u, v) set p(u) := :=V 16: decrease-key for (u, dist(u)) in Q 9: 13: 15:
oo 8 00 8 00 oo 8 DISTANCE a b c d e f g h 00 10 20 30 40 50 60 70 PREDECESSOR a b c d e f g h 0 0 0 0 0 0 0 0 0 10 20 30 4 Ø 50 60 70