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 path from a starting point to all other points in a network that has no cycles (a Directed Acyclic Graph or DAG). This is useful in scheduling tasks where some tasks must be done before others.

🎯 Goal: Build a program in C that finds the shortest distance from a given source node to all other nodes in a DAG using topological sorting.

📋 What You'll Learn

Create a graph using adjacency lists with exact edges and weights

Create an array to store shortest distances initialized properly

Implement topological sorting using DFS with exact function and variable names

Relax edges in topological order to find shortest paths

Print the shortest distances array exactly as specified

💡 Why This Matters

🌍 Real World

Finding shortest paths in DAGs is useful in project scheduling, task ordering, and optimizing workflows where some tasks depend on others.

💼 Career

Understanding shortest path algorithms in DAGs is important for software engineers working on compilers, build systems, and any system that requires dependency resolution.

1

Create the Graph with Adjacency Lists

Create a graph with 6 nodes using adjacency lists. Add these directed edges with weights exactly: 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). Use the struct Edge with fields to and weight, and an array graph of type Edge graph[6][10] with an integer array graph_size[6] to track the number of edges per node.

DSA C

#include 

#define MAX_NODES 6
#define MAX_EDGES 10

typedef struct {
    int to;
    int weight;
} Edge;

Edge graph[MAX_NODES][MAX_EDGES];
int graph_size[MAX_NODES] = {0};

int main() {
    // Add edges to graph here
    // Your code here
    return 0;
}

Hint

Use graph[node][graph_size[node]++] = (Edge){to, weight}; to add edges.

2

Create Distance Array and Visited Array

Create an integer array dist of size 6 and initialize all values to 1000000 (representing infinity). Create an integer array visited of size 6 and initialize all values to 0. Set dist[0] to 0 as the source node distance.

DSA C

#include 

#define MAX_NODES 6
#define MAX_EDGES 10

typedef struct {
    int to;
    int weight;
} Edge;

Edge graph[MAX_NODES][MAX_EDGES];
int graph_size[MAX_NODES] = {0};

int main() {
    graph[0][graph_size[0]++] = (Edge){1, 5};
    graph[0][graph_size[0]++] = (Edge){2, 3};
    graph[1][graph_size[1]++] = (Edge){3, 6};
    graph[1][graph_size[1]++] = (Edge){2, 2};
    graph[2][graph_size[2]++] = (Edge){4, 4};
    graph[2][graph_size[2]++] = (Edge){5, 2};
    graph[2][graph_size[2]++] = (Edge){3, 7};
    graph[3][graph_size[3]++] = (Edge){4, -1};
    graph[4][graph_size[4]++] = (Edge){5, -2};

    // Create dist and visited arrays here
    // Your code here
    return 0;
}

Hint

Use a for loop to set all dist values to 1000000 and all visited values to 0. Then set dist[0] to 0.

3

Implement Topological Sort and Relax Edges

Write a recursive function void dfs(int node, int stack[], int *top) that marks visited[node] as 1, visits all unvisited neighbors using for (int i = 0; i < graph_size[node]; i++), and after visiting neighbors, adds node to stack at index (*top)++. Then in main, create an integer array stack[6] and integer top = 0. Run dfs for all nodes from 0 to 5 if not visited. After that, process nodes in reverse order from stack to relax edges: for each edge from u to v with weight w, if dist[u] + w < dist[v], update dist[v] = dist[u] + w.

DSA C

#include 

#define MAX_NODES 6
#define MAX_EDGES 10

typedef struct {
    int to;
    int weight;
} Edge;

Edge graph[MAX_NODES][MAX_EDGES];
int graph_size[MAX_NODES] = {0};

int dist[MAX_NODES];
int visited[MAX_NODES];

void dfs(int node, int stack[], int *top) {
    // Write DFS to fill stack here
    // Your code here
}

int main() {
    graph[0][graph_size[0]++] = (Edge){1, 5};
    graph[0][graph_size[0]++] = (Edge){2, 3};
    graph[1][graph_size[1]++] = (Edge){3, 6};
    graph[1][graph_size[1]++] = (Edge){2, 2};
    graph[2][graph_size[2]++] = (Edge){4, 4};
    graph[2][graph_size[2]++] = (Edge){5, 2};
    graph[2][graph_size[2]++] = (Edge){3, 7};
    graph[3][graph_size[3]++] = (Edge){4, -1};
    graph[4][graph_size[4]++] = (Edge){5, -2};

    for (int i = 0; i < MAX_NODES; i++) {
        dist[i] = 1000000;
        visited[i] = 0;
    }
    dist[0] = 0;

    int stack[MAX_NODES];
    int top = 0;

    // Run DFS for all nodes
    // Relax edges in topological order
    // Your code here

    return 0;
}

Hint

Use DFS to fill stack with nodes in topological order. Then relax edges in reverse order of stack.

4

Print the Shortest Distances

Print the shortest distances from node 0 to all nodes in order from 0 to 5 using printf. For each node i, print dist[i] followed by a space. If dist[i] is 1000000, print INF instead. End with a newline.

DSA C

#include 

#define MAX_NODES 6
#define MAX_EDGES 10

typedef struct {
    int to;
    int weight;
} Edge;

Edge graph[MAX_NODES][MAX_EDGES];
int graph_size[MAX_NODES] = {0};

int dist[MAX_NODES];
int visited[MAX_NODES];

void dfs(int node, int stack[], int *top) {
    visited[node] = 1;
    for (int i = 0; i = 0; i--) {
        int u = stack[i];
        if (dist[u] != 1000000) {
            for (int j = 0; j < graph_size[u]; j++) {
                int v = graph[u][j].to;
                int w = graph[u][j].weight;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

    // Print shortest distances here
    // Your code here

    return 0;
}

Hint

Use a for loop to print each distance. Print INF if distance is 1000000, else print the distance number. End with a newline.

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