Consider a weighted graph representing a logistics network with cities as nodes (A, B, C, D, E, F) and roads as edges. Starting from node A, the initial tentative distances are given as: A = 0, B = 2, C = 5, and infinity for nodes D, E, and F. Assume that node B (with a distance of 2) has just been finalized in Dijkstra’s algorithm. Now:
(a) Update the tentative distances for the neighbors of node B, which are nodes C and D, given the edge weights B-C = 1 and B-D = 2.
(b) Using the updated distances and considering the remaining edges with weights C-D = 3, C-E = 2, D-E = 1, D-F = 5, and E-F = 3, determine the shortest path from node A to node F and its total distance. Continue applying Dijkstra’s algorithm until node F is finalized.
Question
Given that node B is finalized with a shortest distance of 2 from node A, and the edge weights are B-C = 1 and B-D = 2, update the tentative distances for nodes C and D. Node C previously had a tentative distance of 5, and node D had infinity.
Hint
Hint
Hint
Calculate the new tentative distance to each neighbor of B by adding the distance to B and the edge weight from B to the neighbor. Update only if this new distance is shorter than the current tentative distance.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
- Formula Booklet
Complete Answer
Updated tentative distance for C: 3, Updated tentative distance for D: 4
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Continue Dijkstra’s algorithm to find the shortest path from node A to node F. Using the updated distances from part (a) and the remaining edge weights (C-D = 3, C-E = 2, D-E = 1, D-F = 5, and E-F = 3), finalize the shortest path from A to F and state the total distance.
Hint
Hint
Hint
Proceed by selecting the node with the smallest tentative distance among the unfinalized nodes and repeat the process of updating distances for its neighbors until node F is finalized.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
- Formula Booklet
Complete Answer
Shortest path: A -> B -> D -> E -> F, Total distance: 8
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
