Shortest Path in DAG Using Topological Order in DSA C++ - Build from Scratch

Shortest Path in DAG Using Topological Order

📖 Scenario: You are working on a project to find the shortest travel time between cities connected by one-way roads. The roads form a network without any cycles, meaning you cannot return to a city once you leave it. This kind of network is called a Directed Acyclic Graph (DAG).Your task is to find the shortest time to reach each city starting from the first city using a method called topological order.

🎯 Goal: Build a program that finds the shortest path from the starting city (node 0) to all other cities in a DAG using topological sorting.

📋 What You'll Learn

Create a graph as an adjacency list with exact edges and weights

Create a vector to store shortest distances initialized properly

Implement topological sorting using DFS

Calculate shortest paths using the topological order

Print the shortest distances from the start city to all other cities

💡 Why This Matters

🌍 Real World

Finding shortest paths in networks without cycles is useful in project scheduling, task ordering, and routing where cycles are not allowed.

💼 Career

Understanding shortest path algorithms in DAGs is important for software engineers working on compilers, project management tools, and network routing.

1

Create the graph as an adjacency list

Create a vector of vectors called graph with 6 nodes (0 to 5). Add these directed edges with weights exactly:
From 0 to 1 with weight 5,
From 0 to 2 with weight 3,
From 1 to 3 with weight 6,
From 1 to 2 with weight 2,
From 2 to 4 with weight 4,
From 2 to 5 with weight 2,
From 2 to 3 with weight 7,
From 3 to 4 with weight -1,
From 4 to 5 with weight -2.

DSA C++

// Create graph as adjacency list with edges and weights
// Your code here

Hint

Use vector>> to store edges and weights. Each inner vector holds pairs of (neighbor, weight).

2

Create distance vector and visited vector

Create a vector of integers called dist with size 6, initialized with INT_MAX. Set dist[0] to 0. Also create a vector of booleans called visited with size 6, initialized with false.

DSA C++

#include 
#include 
#include 
using namespace std;

int main() {
    vector>> graph(6);
    graph[0].push_back({1, 5});
    graph[0].push_back({2, 3});
    graph[1].push_back({3, 6});
    graph[1].push_back({2, 2});
    graph[2].push_back({4, 4});
    graph[2].push_back({5, 2});
    graph[2].push_back({3, 7});
    graph[3].push_back({4, -1});
    graph[4].push_back({5, -2});

    // Create dist vector and visited vector
    // Your code here

    return 0;
}

Hint

Use vector dist(6, INT_MAX); and then set dist[0] = 0;. Use vector visited(6, false); for tracking visited nodes.

3

Implement DFS for topological sorting and find shortest paths

Write a recursive function called dfs that takes int node, vector>>& graph, vector& visited, and vector& topo. It should mark node as visited, call itself recursively for all unvisited neighbors, then add node to topo. Then, in main, create a vector topo and call dfs for all nodes from 0 to 5 if not visited. Reverse topo. Finally, use topo to relax edges and update dist for shortest paths.

DSA C++

#include 
#include 
#include 
#include 
using namespace std;

void dfs(int node, vector>>& graph, vector& visited, vector& topo) {
    // Write DFS to fill topo vector
    // Your code here
}

int main() {
    vector>> graph(6);
    graph[0].push_back({1, 5});
    graph[0].push_back({2, 3});
    graph[1].push_back({3, 6});
    graph[1].push_back({2, 2});
    graph[2].push_back({4, 4});
    graph[2].push_back({5, 2});
    graph[2].push_back({3, 7});
    graph[3].push_back({4, -1});
    graph[4].push_back({5, -2});

    vector dist(6, INT_MAX);
    dist[0] = 0;
    vector visited(6, false);

    vector topo;
    // Call dfs for all nodes and reverse topo
    // Relax edges using topo order
    // Your code here

    return 0;
}

Hint

Use DFS to fill topo in post-order. Reverse it to get topological order. Then relax edges in that order to find shortest paths.

4

Print the shortest distances

Print the shortest distances from node 0 to all nodes in order from 0 to 5. For nodes unreachable from 0, print "INF". Use a loop and print each distance separated by a space.

DSA C++

#include 
#include 
#include 
#include 
using namespace std;

void dfs(int node, vector>>& graph, vector& visited, vector& topo) {
    visited[node] = true;
    for (auto& edge : graph[node]) {
        int neighbor = edge.first;
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited, topo);
        }
    }
    topo.push_back(node);
}

int main() {
    vector>> graph(6);
    graph[0].push_back({1, 5});
    graph[0].push_back({2, 3});
    graph[1].push_back({3, 6});
    graph[1].push_back({2, 2});
    graph[2].push_back({4, 4});
    graph[2].push_back({5, 2});
    graph[2].push_back({3, 7});
    graph[3].push_back({4, -1});
    graph[4].push_back({5, -2});

    vector dist(6, INT_MAX);
    dist[0] = 0;
    vector visited(6, false);

    vector topo;
    for (int i = 0; i < 6; i++) {
        if (!visited[i]) {
            dfs(i, graph, visited, topo);
        }
    }
    reverse(topo.begin(), topo.end());

    for (int node : topo) {
        if (dist[node] != INT_MAX) {
            for (auto& edge : graph[node]) {
                int neighbor = edge.first;
                int weight = edge.second;
                if (dist[node] + weight < dist[neighbor]) {
                    dist[neighbor] = dist[node] + weight;
                }
            }
        }
    }

    // Print shortest distances
    // Your code here

    return 0;
}

Hint

Loop through dist and print each distance. Print "INF" if distance is INT_MAX.

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