Shortest Path in DAG Using Topological Order in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances in DAG

What is the output of the following C++ code that finds shortest paths from node 0 in a DAG using topological order?

DSA C++

/*
Graph edges with weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 4 (3), 3 -> 5 (1), 4 -> 3 (1), 4 -> 5 (5)
*/
#include <iostream>
#include <vector>
#include <stack>
#include <limits>
using namespace std;

void topologicalSort(int node, vector<vector<pair<int,int>>>& graph, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for(auto& edge : graph[node]) {
        int v = edge.first;
        if(!visited[v]) topologicalSort(v, graph, visited, st);
    }
    st.push(node);
}

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

    vector<bool> visited(V, false);
    stack<int> st;
    for(int i=0; i<V; i++) {
        if(!visited[i]) topologicalSort(i, graph, visited, st);
    }

    vector<int> dist(V, numeric_limits<int>::max());
    dist[0] = 0;

    while(!st.empty()) {
        int u = st.top();
        st.pop();
        if(dist[u] != numeric_limits<int>::max()) {
            for(auto& edge : graph[u]) {
                int v = edge.first;
                int w = edge.second;
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

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

A 0 2 3 9 6 11

B 0 2 3 7 6 8

C 0 2 4 7 6 8

D 0 2 3 7 5 8

💡 Hint

Trace the topological order and update distances step-by-step from node 0.

The code performs a topological sort and then relaxes edges in that order. Starting from node 0 with distance 0, distances to reachable nodes are updated to shortest possible values. The final distances are: 0 (start), 2 (0->1), 3 (0->1->2), 7 (0->1->2->4->3 or 0->1->3), 6 (0->1->2->4), 8 (0->1->2->4->3->5).

🧠 Conceptual

intermediate

Why use topological order for shortest path in DAG?

Why is topological order used to find shortest paths in a Directed Acyclic Graph (DAG)?

A Because it ensures nodes are processed only after all their dependencies, allowing correct distance updates without cycles.

B Because it sorts nodes by their distance values automatically.

C Because it guarantees the longest path is found first.

D Because it detects cycles in the graph to avoid infinite loops.

💡 Hint

Think about how processing nodes in order affects distance updates.

Topological order processes nodes so that all edges go from earlier to later nodes. This means when we process a node, all nodes that can reach it have already been processed, so distances are finalized and can be used to update the current node's neighbors correctly.

🔧 Debug

advanced

Identify the bug in shortest path code for DAG

What error will the following code produce when finding shortest paths in a DAG using topological order?

DSA C++

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

void topologicalSort(int node, vector<vector<pair<int,int>>>& graph, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for(auto edge : graph[node]) {
        int v = edge.first; // <-- fixed line
        if(!visited[v]) topologicalSort(v, graph, visited, st);
    }
    st.push(node);
}

int main() {
    int V = 3;
    vector<vector<pair<int,int>>> graph(V);
    graph[0].push_back({1,5});
    graph[1].push_back({2,3});

    vector<bool> visited(V, false);
    stack<int> st;
    for(int i=0; i<V; i++) {
        if(!visited[i]) topologicalSort(i, graph, visited, st);
    }

    vector<int> dist(V, numeric_limits<int>::max());
    dist[0] = 0;

    while(!st.empty()) {
        int u = st.top();
        st.pop();
        if(dist[u] != numeric_limits<int>::max()) {
            for(auto edge : graph[u]) {
                int v = edge.first;
                int w = edge.second;
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

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

A No error, outputs: 0 5 8

B Syntax error due to missing semicolon

C Logical error: distances not updated correctly

D Runtime error due to accessing wrong edge element

💡 Hint

Check how edge elements are accessed in topologicalSort function.

In topologicalSort, the code uses edge.second as the next node, but edge.first is the node index and edge.second is the weight. Accessing edge.second as node index causes wrong memory access or runtime error.

❓ Predict Output

advanced

Output of shortest path distances with unreachable nodes

What is the output of the following code that finds shortest paths from node 0 in a DAG with some unreachable nodes?

DSA C++

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

void topologicalSort(int node, vector<vector<pair<int,int>>>& graph, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for(auto& edge : graph[node]) {
        int v = edge.first;
        if(!visited[v]) topologicalSort(v, graph, visited, st);
    }
    st.push(node);
}

int main() {
    int V = 5;
    vector<vector<pair<int,int>>> graph(V);
    graph[0].push_back({1,3});
    graph[1].push_back({2,4});
    // Node 3 and 4 are disconnected

    vector<bool> visited(V, false);
    stack<int> st;
    for(int i=0; i<V; i++) {
        if(!visited[i]) topologicalSort(i, graph, visited, st);
    }

    vector<int> dist(V, numeric_limits<int>::max());
    dist[0] = 0;

    while(!st.empty()) {
        int u = st.top();
        st.pop();
        if(dist[u] != numeric_limits<int>::max()) {
            for(auto& edge : graph[u]) {
                int v = edge.first;
                int w = edge.second;
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

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

A 0 3 7 INF 0

B 0 3 7 0 0

C 0 3 7 INF INF

D 0 3 7 3 3

💡 Hint

Nodes 3 and 4 are disconnected, so their distances remain infinite.

Nodes 3 and 4 are unreachable from node 0, so their distances remain infinity (INF). Nodes 1 and 2 have distances 3 and 7 respectively from node 0.

🧠 Conceptual

expert

Time complexity of shortest path in DAG using topological order

What is the time complexity of finding shortest paths in a DAG using topological order and edge relaxation?

A O(V + E), where V is vertices and E is edges

B O(V^2), because each vertex is compared with all others

C O(V!), because of permutations in topological sorting

D O(E log V), due to priority queue operations

💡 Hint

Consider the cost of topological sort plus edge relaxation.

Topological sort takes O(V + E) time. Relaxing edges once in topological order also takes O(E). So total time is O(V + E).

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