Printing the Actual Shortest Path with Dijkstra Algorithm

Need not just distances but the real route? Learn how to extend Dijkstra’s algorithm to reconstruct the shortest path from node 1 to node n. We break down the idea, annotate the Python code, walk through the sample graph [1-4-3-5], and cover complexity.

Here’s the [Problem Link] to begin with.

1. What are we doing?

• Input –
  • n : number of vertices (1-indexed)
  • edges : undirected weighted edges [u, v, w]
• Goal –
  • Use Dijkstra to find the minimum-cost path from vertex 1 to vertex n.
  • Return the list of nodes in order; if n is unreachable, return [-1].

2. Quick example

n = 5
edges = [
  [1,2,2], [2,5,5],
  [2,3,4], [1,4,1],
  [4,3,3], [3,5,1]
]

Shortest path from 1 to 5 is

1  →  4  →  3  →  5
 (1)   (3)   (1)     total = 5

print(shortest_path(...)) outputs

[1, 4, 3, 5]

3. Intuition & approach

3.1 Plain Dijkstra recap

• Keep a min-heap of (distance, node).
• Pop the lightest node, relax its edges; distances only improve.

3.2 How to retrieve the actual path

• For every relaxation that really improves distance[v], store the predecessor: pythonCopyEditparent[v] = u
• After the algorithm ends, parent[x] tells you the previous vertex on the shortest route to x.
• To reconstruct the path to n:
  • Start at n, push it onto a list.
  • Follow parent pointers backwards until you reach 1.
  • Reverse the list.

If distance[n] stayed at ∞, vertex n is unreachable—return [-1].

4. Code

import heapq
import sys


def shortest_path(n, m, edges):
    # 1. Build undirected adjacency list
    adj_list = [[] for _ in range(n + 1)]
    for u, v, wt in edges:
        adj_list[u].append([v, wt])
        adj_list[v].append([u, wt])

    # 2. Dijkstra initialisation
    distance = [sys.maxsize] * (n + 1)
    distance[1] = 0                          # source vertex

    parent = [i for i in range(n + 1)]       # parent[i] = predecessor of i

    pq = []                                  # min-heap of (dist, node)
    heapq.heappush(pq, (0, 1))

    # 3. Main loop
    while pq:
        dist, node = heapq.heappop(pq)

        if dist != distance[node]:           # ignore stale heap entries
            continue

        for adjNode, wt in adj_list[node]:
            new_dist = dist + wt
            if new_dist < distance[adjNode]:  # relaxation succeeds
                distance[adjNode] = new_dist
                heapq.heappush(pq, (new_dist, adjNode))
                parent[adjNode] = node        # record the path

    # 4. Reconstruct path or report unreachable
    if distance[n] == sys.maxsize:
        return [-1]

    path = []
    node = n
    while parent[node] != node:              # follow parents back to 1
        path.append(node)
        node = parent[node]
    path.append(1)
    path.reverse()
    return path


# ----- demo run -----
n = 5
m = 6
edges = [
    [1, 2, 2], [2, 5, 5],
    [2, 3, 4], [1, 4, 1],
    [4, 3, 3], [3, 5, 1]
]
print(shortest_path(n, m, edges))            # ➜ [1, 4, 3, 5]

5. Dry run on the sample graph

Backward chain 5 ← 3 ← 4 ← 1 reversed ⇒ [1,4,3,5].

6. Complexity

7. Key takeaways

• Path reconstruction needs only one extra parent array.
• Always update parent[v] only when you genuinely shorten distance[v].
• For undirected graphs, remember to insert edges both ways in adj_list.
• Make sure to skip stale heap entries (dist != distance[node]) for efficiency.

Armed with this pattern you can extract not just the cost but the exact sequence of nodes for any shortest-path query with Dijkstra’s algorithm.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.