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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances from source in DAG

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

DSA C

#include <stdio.h>
#include <limits.h>
#define V 6

void shortestPath(int graph[V][V], int src) {
    int dist[V];
    int visited[V] = {0};
    int stack[V], top = -1;

    // Function to perform DFS and fill stack
    void dfs(int v) {
        visited[v] = 1;
        for (int i = 0; i < V; i++) {
            if (graph[v][i] != INT_MAX && !visited[i]) {
                dfs(i);
            }
        }
        stack[++top] = v;
    }

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

    for (int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[src] = 0;

    while (top >= 0) {
        int u = stack[top--];
        if (dist[u] != INT_MAX) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }

    for (int i = 0; i < V; i++) {
        if (dist[i] == INT_MAX) printf("INF ");
        else printf("%d ", dist[i]);
    }
    printf("\n");
}

int main() {
    int graph[V][V] = {
        {INT_MAX, 5, 3, INT_MAX, INT_MAX, INT_MAX},
        {INT_MAX, INT_MAX, 2, 6, INT_MAX, INT_MAX},
        {INT_MAX, INT_MAX, INT_MAX, 7, 4, 2},
        {INT_MAX, INT_MAX, INT_MAX, INT_MAX, -1, 1},
        {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, -2},
        {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX}
    };
    shortestPath(graph, 0);
    return 0;
}

A "0 5 3 10 7 5 "

B "0 5 3 9 6 4 "

C "0 INF INF INF INF INF "

D "0 5 3 13 7 5 "

💡 Hint

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

The code performs a DFS to get topological order, then relaxes edges in that order. The shortest distances from node 0 to others are: 0 (to itself), 5 (via edge 0->1), 3 (0->2), 10 (0->2->3), 7 (0->2->4), 5 (0->2->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 sorts vertices by their distance from the source automatically.

B Because it ensures we process vertices only after all their predecessors, allowing correct distance updates without cycles.

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

D Because it finds the longest path in the graph first.

💡 Hint

Think about how processing order affects distance updates in graphs without cycles.

Topological order processes each vertex after all vertices that lead into it, so when we update distances, all shortest paths to predecessors are already known. This works only in DAGs because they have no cycles.

🔧 Debug

advanced

Identify the bug causing incorrect shortest path output

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

DSA C

void shortestPath(int graph[V][V], int src) {
    int dist[V];
    int visited[V] = {0};
    int stack[V], top = -1;

    void dfs(int v) {
        visited[v] = 1;
        for (int i = 0; i < V; i++) {
            if (graph[v][i] != INT_MAX && !visited[i]) {
                dfs(i);
            }
        }
        stack[++top] = v;
    }

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

    for (int i = 0; i < V; i++) dist[i] = INT_MAX;
    dist[src] = 0;

    while (top >= 0) {
        int u = stack[top--];
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    for (int i = 0; i < V; i++) {
        if (dist[i] == INT_MAX) printf("INF ");
        else printf("%d ", dist[i]);
    }
    printf("\n");
}

A The graph adjacency matrix uses 0 for no edge instead of INT_MAX.

B The DFS does not mark nodes as visited, causing infinite recursion.

C The stack is not used to store topological order.

D The code does not check if dist[u] is INT_MAX before relaxing edges, causing invalid additions.

💡 Hint

Check the relaxation step carefully for invalid distance updates.

If dist[u] is INT_MAX (meaning unreachable), adding graph[u][v] causes overflow or wrong values. The code must check dist[u] != INT_MAX before relaxing edges.

📝 Syntax

advanced

Identify the syntax error in the topological sort DFS function

Which option contains the syntax error in this DFS function used for topological sorting?

DSA C

void dfs(int v) {
    visited[v] = 1
    for (int i = 0; i < V; i++) {
        if (graph[v][i] != INT_MAX && !visited[i]) {
            dfs(i);
        }
    }
    stack[++top] = v;
}

A Missing braces around for loop body

B Incorrect increment operator in stack[++top]

C Missing semicolon after visited[v] = 1

D Missing return type for dfs function

💡 Hint

Look carefully at each line for missing punctuation.

The line 'visited[v] = 1' is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Number of shortest paths from source to target in DAG

Given a DAG with weighted edges (all weights positive), how can you modify the shortest path algorithm using topological order to also count the number of distinct shortest paths from source to each vertex?

A Maintain a count array initialized with 0 except source=1; when relaxing edges, if a shorter path is found, update count[v] = count[u]; if equal path length found, add count[u] to count[v].

B Use a BFS instead of topological order and increment count for each visited node.

C Store all paths explicitly in a list and count them after shortest path calculation.

D Run the shortest path algorithm multiple times, each time removing edges used in previous shortest paths.

💡 Hint

Think about how to track number of ways while updating shortest distances.

By maintaining a count array, we track how many shortest paths reach each vertex. When a shorter path is found, reset count; when an equal path is found, add counts. This works efficiently with topological order.

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 guarantees the graph has cycles.

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

C. It sorts vertices by their weights.

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

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that every directed edge goes from an earlier vertex to a later one, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order allows updating shortest distances without revisiting nodes, making the algorithm efficient.

3. Final Answer:

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

4. Quick Check:

   Topological order = linear processing [OK]

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

Common Mistakes:

• Thinking DAG has cycles
• Confusing topological order with sorting by weights
• Assuming it finds longest path by default

2. Which of the following C code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices?

easy

A. int dist[5] = {0, 0, 0, 0, 0};

B. int dist[5] = {-1, -1, -1, -1, -1};

C. int dist[5]; for(int i=0; i<5; i++) dist[i] = INT_MAX;

D. int dist[5] = {INT_MIN, INT_MIN, INT_MIN, INT_MIN, INT_MIN};

Solution

1. Step 1: Understand initialization for shortest path

   Distances should start as very large values (infinity) to represent unknown paths.

2. Step 2: Identify correct initialization

   Using INT_MAX sets all distances to a large number, suitable for shortest path updates.

3. Final Answer:

   int dist[5]; for(int i=0; i<5; i++) dist[i] = INT_MAX; -> Option C

4. Quick Check:

   Initialize distances to INT_MAX [OK]

Hint: Initialize distances with INT_MAX for shortest path [OK]

Common Mistakes:

• Initializing distances to zero (wrong for shortest path)
• Using INT_MIN which is for max path, not min
• Using -1 which can cause incorrect comparisons

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 3 (3)
If we run shortest path from vertex 0 using topological order, 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 can be [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, dist[3]=2+7=9.
   From 2: dist[3]=min(9,3+3)=6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

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

Common Mistakes:

• Not updating dist[2] to 3 from 1->2 edge
• Ignoring better path from 2 to 3
• Using wrong topological order

4. Given this code snippet for shortest path in DAG, what is the error?

for (int i = 0; i < V; i++) {
  for (auto edge : adj[i]) {
    int v = edge.first;
    int weight = edge.second;
    if (dist[i] + weight < dist[v])
      dist[v] = dist[i] + weight;
  }
}

Assume dist is initialized and adj is adjacency list.

medium

A. The outer loop should follow topological order, not 0 to V-1.

B. The weight variable is not assigned correctly.

C. The condition should be dist[v] + weight < dist[i].

D. The adjacency list should be reversed.

Solution

1. Step 1: Check loop order for shortest path in DAG

   The outer loop must process vertices in topological order to ensure correct relaxation.

2. Step 2: Identify the error in loop order

   Looping from 0 to V-1 may not respect topological order, causing incorrect distance updates.

3. Final Answer:

   The outer loop should follow topological order, not 0 to V-1. -> Option A

4. Quick Check:

   Use topological order for outer loop [OK]

Hint: Always loop vertices in topological order for DAG shortest path [OK]

Common Mistakes:

• Ignoring topological order in loops
• Mixing up edge weight usage
• Reversing adjacency list unnecessarily

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

hard

A. 7

B. 8

C. 4

D. 5

Solution

1. Step 1: Determine topological order and initialize distances

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

2. Step 2: Relax edges in order

   From 0: dist[1]=5, dist[2]=3.
   From 1: dist[3]=min(inf,5+6=11)=11, dist[2]=min(3,5+2=7)=3 (unchanged).
   From 2: dist[4]=min(inf,3+4=7)=7, dist[5]=min(inf,3+2=5)=5, dist[3]=min(11,3+7=10)=10.
   From 3: dist[4]=min(7,10+(-1)=9)=7 (unchanged).
   From 4: dist[5]=min(5,7+(-2)=5)=5 (unchanged).

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Shortest distance to 5 = 5 [OK]

Hint: Relax edges in topological order, watch negative weights carefully [OK]

Common Mistakes:

• Ignoring negative weights in relaxation
• Not updating distances with better paths
• Wrong topological order causing errors