- (13%) Consider a directed graph G, consisting of four vertices labeled A, B, C, and D. The graph has the following edges with their respective weights: edge from A to B with weight 2, edge from B to D with weight 1, edge from A to C with weight -4, and edge from C to B with weight 3.
Given the Pseudo Code for Bellman-Ford Algorithm: Input: Graph G with vertices V and edges E, source vertex s Output: Shortest path from s to other vertices, or detection of a negative cycle
1. function BellmanFord(G, s):
2. // Initialization
3. for each vertex v in V do
4. dist[v] := (1)
5. prev[v] := undefined
6. dist[s] := (2)
7.
8. // Main Loop
9. for i from 1 to |V|-1:
10. for each edge (u, v) in E:
11. if dist[u] + weight(u, v) (3) dist[v]:
12. dist[v] := dist[u] + weight(u, v)
13. prev[v] := u
14.
15. // Check for negative weight cycles
16. for each edge (u, v) in E:
17. if dist[u] + weight(u, v) (4) dist[v]:
18. return "Graph contains a negative weight cycle"
19.
20. return dist, prev
(A) [4%] What values should be filled in to (1), (2), (3), (4) in the Pseudo Code? (1) ________ (2) ________ (3) ________ (4) ________
(B) [3%] Let the source vertex be 'A'. After the first iteration of the main loop, what is the updated value of dist[C]?
dist[C] := ________
(C) [3%] Let the source vertex be 'A'. In the second iteration of the main loop, after processing the edge from C to B, what will be the new value of dist[B]?
dist[B] := ________
(D) [3%] Let the source vertex be 'A'. What will be the final value of dist[D] after the algorithm completes its execution?
dist[D] := ________