Shortest Path in DAG Using Topological Order in DSA C++

Mental Model

We find the shortest path in a graph with no cycles by first ordering nodes so all edges go forward, then updating shortest distances step-by-step.

Analogy: Imagine tasks that must be done in order, like cooking steps. You first list steps so each comes after its prerequisites, then find the quickest way to finish all tasks by checking each step once in order.

0 -> 1 -> 2 -> 3 -> null
↑topological order
Distances updated along this order

Dry Run Walkthrough

Input: Graph edges with weights: 0->1(2), 0->2(4), 1->2(1), 1->3(7), 2->3(3); start node 0

Goal: Find shortest distances from node 0 to all others using topological order

Step 1: Perform topological sort to order nodes: 0, 1, 2, 3

Order: [0, 1, 2, 3]

Why: We need to process nodes so all edges go forward, no backward edges

Step 2: Initialize distances: dist[0]=0, others=∞

dist: [0, ∞, ∞, ∞]

Why: Start node distance is zero, others unknown

Step 3: Process node 0: update dist[1]=2, dist[2]=4

dist: [0, 2, 4, ∞]

Why: From 0, edges to 1 and 2 update their distances

Step 4: Process node 1: update dist[2]=3 (min of 4 and 2+1), dist[3]=9

dist: [0, 2, 3, 9]

Why: From 1, edge to 2 improves dist, edge to 3 sets dist

Step 5: Process node 2: update dist[3]=6 (min of 9 and 3+3)

dist: [0, 2, 3, 6]

Why: From 2, edge to 3 improves dist

Step 6: Process node 3: no outgoing edges, distances unchanged

dist: [0, 2, 3, 6]

Why: No further updates possible

Result:

distances: 0 -> 2 -> 3 -> 6

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <stack>
#include <limits>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<pair<int, int>>> adj;

    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v, int weight) {
        adj[u].push_back({v, weight});
    }

    void topologicalSortUtil(int v, vector<bool> &visited, stack<int> &Stack) {
        visited[v] = true;
        for (auto &edge : adj[v]) {
            int node = edge.first;
            if (!visited[node]) {
                topologicalSortUtil(node, visited, Stack); // recurse to neighbors
            }
        }
        Stack.push(v); // push after visiting neighbors
    }

    void shortestPath(int start) {
        stack<int> Stack;
        vector<bool> visited(V, false);

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, Stack); // get topological order
            }
        }

        vector<int> dist(V, numeric_limits<int>::max());
        dist[start] = 0; // distance to start is zero

        while (!Stack.empty()) {
            int u = Stack.top();
            Stack.pop();

            if (dist[u] != numeric_limits<int>::max()) {
                for (auto &edge : adj[u]) {
                    int v = edge.first;
                    int weight = edge.second;
                    if (dist[v] > dist[u] + weight) {
                        dist[v] = dist[u] + weight; // update shorter distance
                    }
                }
            }
        }

        for (int i = 0; i < V; i++) {
            if (dist[i] == numeric_limits<int>::max())
                cout << "INF" << " ";
            else
                cout << dist[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 4);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 7);
    g.addEdge(2, 3, 3);

    g.shortestPath(0);
    return 0;
}

topologicalSortUtil(node, visited, Stack); // recurse to neighbors

advance DFS to neighbors to build topological order

Stack.push(v); // push after visiting neighbors

push node after all descendants to ensure correct order

dist[start] = 0; // distance to start is zero

initialize start node distance

if (dist[u] != numeric_limits<int>::max()) {

process only nodes reachable from start

if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; }

relax edge to update shortest distance

Output

0 2 3 6 

Complexity Analysis

Time: O(V + E) because we do a topological sort (O(V+E)) and then relax edges once each (O(E))

Space: O(V + E) for adjacency list and auxiliary data structures like stack and distance array

vs Alternative: Compared to Dijkstra's algorithm, this is faster for DAGs because no priority queue is needed and edges are relaxed once in topological order

Edge Cases

Empty graph (no nodes)

No processing occurs, output is empty

DSA C++

for (int i = 0; i < V; i++) { if (!visited[i]) { topologicalSortUtil(i, visited, Stack); } }

Graph with unreachable nodes from start

Distances to unreachable nodes remain INF

DSA C++

if (dist[u] != numeric_limits<int>::max()) {

Graph with single node

Distance to start node is zero, no edges to relax

DSA C++

dist[start] = 0;

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to process nodes once in order and relax edges efficiently.

Common Mistakes

Mistake: Not performing topological sort before relaxing edges, causing incorrect distances or infinite loops
Fix: Always run topological sort first to ensure edges go forward and each node is processed after its dependencies

Mistake: Updating distances for nodes not reachable from start, leading to incorrect results
Fix: Check if current node distance is not infinity before relaxing edges

Summary

Finds shortest paths in a directed acyclic graph by processing nodes in topological order.

Use when the graph has no cycles and you want efficient shortest path calculation.

The key is to order nodes so all edges go forward, allowing one pass to update distances.

Practice

1. What is the main advantage of using topological order to find the shortest path in a Directed Acyclic Graph (DAG)?

easy

A. It allows processing vertices in a linear order without revisiting nodes.

B. It guarantees the graph has no cycles.

C. It finds the longest path instead of the shortest path.

D. It works only for undirected graphs.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that all edges go from earlier to later vertices, allowing linear processing.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order ensures each vertex is relaxed once, avoiding revisits and cycles.

3. Final Answer:

   It allows processing vertices in a linear order without revisiting nodes. -> Option A

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once in DAG [OK]

Common Mistakes:

• Thinking it works for graphs with cycles
• Confusing shortest path with longest path
• Assuming it works for undirected graphs

2. Which of the following C++ code snippets correctly initializes the distance array for shortest path calculation in a DAG with n vertices, assuming source vertex is 0?

easy

A. std::vector<int> dist(n, 0); dist[0] = INT_MAX;

B. std::vector<int> dist(n, INT_MAX); dist[0] = 0;

C. int dist[n]; for(int i=0; i

D. std::vector<int> dist(n); dist[0] = 0;

Solution

1. Step 1: Initialize distances with maximum value

   Distances should start as infinity (INT_MAX) except source which is 0.

2. Step 2: Check code correctness

   std::vector<int> dist(n, INT_MAX); dist[0] = 0; correctly sets all distances to INT_MAX and source distance to 0.

3. Final Answer:

   std::vector<int> dist(n, INT_MAX); dist[0] = 0; -> Option B

4. Quick Check:

   Distance init = INT_MAX except source 0 [OK]

Hint: Initialize all distances to INT_MAX except source 0 [OK]

Common Mistakes:

• Setting source distance to INT_MAX
• Initializing distances to zero
• Not using vector or uninitialized array

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 3 (3)
Using topological order starting from vertex 0, what is the shortest distance to vertex 3?

medium

A. 6

B. 7

C. 9

D. 10

Solution

1. Step 1: Find topological order and initialize distances

   Topological order: 0, 1, 2, 3. Initialize dist[0]=0, others = infinity.

2. Step 2: Relax edges in topological order

   From 0: dist[1]=2, dist[2]=4
   From 1: dist[2]=min(4, 2+1=3)=3, dist[3]=2+7=9
   From 2: dist[3]=min(9, 3+3=6)=6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

Hint: Relax edges in topological order to update shortest distances [OK]

Common Mistakes:

• Not updating dist[2] to 3 via vertex 1
• Ignoring relaxation from vertex 2 to 3
• Using wrong topological order

4. The following code snippet attempts to find shortest paths in a DAG but produces incorrect results. What is the bug?

std::vector<int> dist(n, INT_MAX);
dist[source] = 0;
for (int u : topoOrder) {
  for (auto &edge : graph[u]) {
    int v = edge.first, w = edge.second;
    if (dist[v] > dist[u] + w) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. The distance array is not initialized properly.

B. The graph edges are not relaxed in topological order.

C. The source vertex distance is not set to zero.

D. The code does not check if dist[u] is INT_MAX before adding w.

Solution

1. Step 1: Analyze relaxation condition

   The code adds w to dist[u] without checking if dist[u] is INT_MAX, causing overflow.

2. Step 2: Identify missing check

   Before relaxing edges, must check dist[u] != INT_MAX to avoid invalid addition.

3. Final Answer:

   The code does not check if dist[u] is INT_MAX before adding w. -> Option D

4. Quick Check:

   Check dist[u] != INT_MAX before relaxation [OK]

Hint: Always check dist[u] != INT_MAX before adding edge weight [OK]

Common Mistakes:

• Assuming initialization is wrong
• Thinking topological order is incorrect
• Forgetting to set source distance

5. Given a DAG with vertices 0 to 4 and edges:
0->1(3), 0->2(6), 1->2(4), 1->3(4), 2->3(8), 3->4(2)
Using topological order, what is the shortest path distance from vertex 0 to vertex 4?

hard

A. 13

B. 11

C. 9

D. 14

Solution

1. Step 1: Determine topological order and initialize distances

   Topological order: 0,1,2,3,4. Initialize dist[0]=0, others = infinity.

2. Step 2: Relax edges in order

   From 0: dist[1]=3, dist[2]=6
   From 1: dist[2]=min(6,3+4=7)=6, dist[3]=3+4=7
   From 2: dist[3]=min(7,6+8=14)=7
   From 3: dist[4]=7+2=9

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Shortest path to 4 = 9 [OK]

Hint: Relax edges stepwise in topological order to find shortest path [OK]

Common Mistakes:

• Not updating dist[3] correctly
• Choosing longer path via vertex 2
• Misordering topological sort