Subject: Data Structure

Question:

Problem statement: Consider the following graph: 1 B 5 3 3 s 2 0 t 2 1 D 4 Start with node s and apply the Dijkstra's algorithm step by step. (a) Show the priority queue at each step of traversing a node. (b) Also, show final paths (along with the path length) from node 's' to every other reachable node. An example solution with starting node = 'A' is as below: Dijkstra's Shortest Paths: A-> B (Path length/cost: 1) A-> B>D->t(Path length/cost: 2) A-> B -> D (Path length/cost: 1) Priority Queue (Step-by-step): Dequeued node Step 0 1 2 3 4 A B D Priority queue [AO] [B 1] [D 1], [t 4] [t 2] > t