G-35. Print Shortest Path - Dijkstra's Algorithm

This chapter covers how to extend Dijkstra's shortest path algorithm to not only compute the minimum distance value between a source and a destination node in a weighted undirected graph, but also to explicitly reconstruct and return the exact sequence of vertices (the path) taken.

1. Why Do We Need Path Reconstruction?

• Standard Dijkstra Limitation: Standard Dijkstra's algorithm tells us the minimum cost (e.g., a total distance of 5) required to travel from a source node to a destination node.
• Real-World Requirement: In routing, navigation systems, and network packet delivery, knowing the numeric cost is insufficient; users and systems need the exact sequence of nodes (e.g., 1 -> 4 -> 3 -> 5) to traverse.
• The Core Challenge: When relaxing edges and popping nodes from a priority queue based on greedy choices, we lose history. We must capture "where am I coming from?" during traversal.

2. Core Mental Model & The "Parent Array" Analogy

To remember the path without re-running searches, we use a concept borrowed from Dynamic Programming and Breadth-First Search: Caching via a Parent Array.

Real-Life Analogy: Breadcrumb Trail / Postal Forwarding

Imagine walking through a massive labyrinth from a starting gate ($1$) to an exit gate ($n$).

• As you explore each room, you leave a sticky note on the door telling yourself: "I came into this room from Room X."
• When you finally reach the exit room ($n$), you don't guess your way back. You simply look at the sticky note on the exit room to find the previous room, go there, look at its sticky note, and repeat until you arrive back at the starting gate.
• Reversing that recorded chain gives you your exact outward path.

3. Problem Statement & Graph Setup

• Graph Type: Weighted, undirected graph with $n$ vertices (1-indexed, nodes $1$ to $n$) and $m$ edges.
• Source Vertex: Always node 1.
• Destination Vertex: Always node n (e.g., node 5).
• Unreachable Condition: If the destination is unreachable (distance remains infinity), return a list containing a single element: [-1].

4. Initial Data Structures Configuration

Before running Dijkstra's algorithm, we initialize three primary data structures:

1. Priority Queue (pq): A min-heap storing pairs of (current_distance, node) to always greedily process the currently known shortest path.
2. Distance Array (dist): An array of size n + 1 initialized to infinity (or a very large integer), with dist[1] = 0.
3. Parent Array (parent): An array of size n + 1 initialized such that every node points to itself: parent[i] = i. This acts as our historical breadcrumb map.

5. Step-by-Step Graph Traversal & Parent Updating

Let's trace how the parent array updates dynamically when a shorter path is discovered:

Detailed Trace Example (Nodes 1 to 5)

1. Start at Node 1: dist[1] = 0, parent[1] = 1. Push (0, 1) to priority queue.
2. Pop (0, 1):
   • Visit neighbor 2: New dist = $0 + 2 = 2$. Update dist[2] = 2, parent[2] = 1. Push (2, 2).
   • Visit neighbor 4: New dist = $0 + 4 = 4$. Update dist[4] = 4, parent[4] = 1. Push (4, 4).
3. Pop (2, 2) (Smallest distance):
   • Visit neighbor 5: New dist = $2 + 5 = 7$. Update dist[5] = 7, parent[5] = 2. Push (7, 5).
4. Pop (4, 4):
   • Visit neighbor 3: New dist = $4 + 3 = 7$ (Wait, can we do better? Let's check: edge from 4 to 3 has weight 1, total = $4 + 1 = 5$). Update dist[3] = 5, parent[3] = 4. Push (5, 3).
5. Pop (5, 3):
   • Visit neighbor 5: New dist = $5 + 1 = 6$. Wait! Previous distance to 5 was $7$. Since $6 < 7$, we update dist[5] = 6 (or lower depending on weights, e.g., total path weight 5 via node 3) and update parent[5] = 3. Push to PQ.

When the priority queue empties, our parent array holds the exact chain of backward links needed to reconstruct the path.

6. Path Backtracking Workflow

Once the algorithm finishes and confirms node $n$ is reachable, we backtrack from destination $n$ to source $1$:

7. Implementation Code (C++ & Java Equivalent Structure)

C++ Implementation

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> shortestPath(int n, int m, vector<vector<int>>& edges) {
        // 1. Create adjacency list for weighted undirected graph
        vector<vector<pair<int, int>>> adj(n + 1);
        for (auto& it : edges) {
            adj[it[0]].push_back({it[1], it[2]});
            adj[it[1]].push_back({it[0], it[2]});
        }
        
        // 2. Initialize Priority Queue, Distance Array, and Parent Array
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> dist(n + 1, 1e9);
        vector<int> parent(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        dist[1] = 0;
        pq.push({0, 1});
        
        // 3. Dijkstra's Algorithm Loop
        while (!pq.empty()) {
            auto it = pq.top();
            pq.pop();
            int dis = it.first;
            int node = it.second;
            
            for (auto iter : adj[node]) {
                int adjNode = iter.first;
                int edgeWeight = iter.second;
                
                if (dis + edgeWeight < dist[adjNode]) {
                    dist[adjNode] = dis + edgeWeight;
                    pq.push({dist[adjNode], adjNode});
                    parent[adjNode] = node; // Record where we came from
                }
            }
        }
        
        // 4. Check if destination is reachable
        if (dist[n] == 1e9) {
            return {-1};
        }
        
        // 5. Backtrack from destination (n) to source (1)
        vector<int> path;
        int node = n;
        while (parent[node] != node) {
            path.push_back(node);
            node = parent[node];
        }
        path.push_back(1); // Add the source node
        
        // 6. Reverse to get path from source to destination
        reverse(path.begin(), path.end());
        return path;
    }
};

8. Complexity Analysis

Summary and Key Takeaways

• Core Distinction: Finding the shortest path value requires only Dijkstra's distance comparison, but printing the path requires keeping track of historical lineage via a parent array.
• Parent Array Initialization: Every node must initially point to itself (parent[i] = i), serving as the termination condition during backtracking.
• Dynamic Updates: Whenever a shorter path to an adjacent node is discovered (dis + edgeWeight < dist[adjNode]), update both the dist array and set parent[adjNode] = node.
• Backtracking Direction: Always backtrack from the destination node $n$ back to the source node $1$ using the parent pointers.
• Reversal Step: Because backtracking collects nodes in reverse order (Destination $\rightarrow$ Source), you must reverse the resulting list before returning the final path.
• Unreachable Handling: If the destination distance remains at infinity (1e9), immediately return [-1] as specified by constraints.
• Time Complexity Balance: Adding path reconstruction adds a negligible $O(N)$ linear pass on top of standard $O(E \log V)$ Dijkstra performance.