Shortest Path in DAG Using Topological Order in DSA C

Mental Model

We find the shortest path in a graph with no cycles by visiting nodes in order so all edges go forward, updating shortest distances as we go.

Analogy: Imagine a line of dominoes set up so each domino can only knock down the next ones ahead, never behind. We knock them down in order, making sure each domino's fall time is the shortest possible.

Graph (DAG):
0 -> 1 -> 3
 ↓    ↓
  2 -> 4

Topological order: 0 -> 1 -> 2 -> 3 -> 4

Dry Run Walkthrough

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

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

Step 1: Find topological order of nodes

Topological order: 0 -> 1 -> 2 -> 3 -> 4

Why: We must process nodes so all edges go forward to update shortest paths correctly

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 give direct 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[2], edge to 3 sets dist[3]

Step 5: Process node 2: update dist[4]=6

dist: [0, 2, 3, 9, 6]

Why: From 2, edge to 4 sets dist[4]

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

dist: [0, 2, 3, 9, 6]

Why: From 3, edge to 4 does not improve dist[4]

Step 7: Process node 4: no outgoing edges

dist: [0, 2, 3, 9, 6]

Why: No further updates possible

Result:

Final shortest distances: 0 -> 0, 1 -> 2, 2 -> 3, 3 -> 9, 4 -> 6

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_NODES 5

// Edge structure
typedef struct Edge {
    int to;
    int weight;
    struct Edge* next;
} Edge;

// Graph structure: adjacency list
typedef struct Graph {
    Edge* edges[MAX_NODES];
} Graph;

// Add edge to graph
void add_edge(Graph* g, int from, int to, int weight) {
    Edge* e = (Edge*)malloc(sizeof(Edge));
    e->to = to;
    e->weight = weight;
    e->next = g->edges[from];
    g->edges[from] = e;
}

// Stack for topological sort
typedef struct Stack {
    int data[MAX_NODES];
    int top;
} Stack;

void push(Stack* s, int val) {
    s->data[++(s->top)] = val;
}

int pop(Stack* s) {
    return s->data[(s->top)--];
}

// DFS for topological sort
void dfs(Graph* g, int node, int visited[], Stack* stack) {
    visited[node] = 1;
    for (Edge* e = g->edges[node]; e != NULL; e = e->next) {
        if (!visited[e->to]) {
            dfs(g, e->to, visited, stack);
        }
    }
    push(stack, node); // push after visiting all descendants
}

// Find topological order
void topological_sort(Graph* g, int order[]) {
    int visited[MAX_NODES] = {0};
    Stack stack;
    stack.top = -1;
    for (int i = 0; i < MAX_NODES; i++) {
        if (!visited[i]) {
            dfs(g, i, visited, &stack);
        }
    }
    // Pop from stack to get order
    for (int i = 0; i < MAX_NODES; i++) {
        order[i] = pop(&stack);
    }
}

// Shortest path in DAG using topological order
void shortest_path_dag(Graph* g, int start, int dist[]) {
    int order[MAX_NODES];
    topological_sort(g, order);

    // Initialize distances
    for (int i = 0; i < MAX_NODES; i++) {
        dist[i] = INT_MAX;
    }
    dist[start] = 0;

    // Relax edges in topological order
    for (int i = 0; i < MAX_NODES; i++) {
        int u = order[i];
        if (dist[u] != INT_MAX) {
            for (Edge* e = g->edges[u]; e != NULL; e = e->next) {
                int v = e->to;
                int w = e->weight;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }
}

int main() {
    Graph g = {0};
    add_edge(&g, 0, 1, 2);
    add_edge(&g, 0, 2, 4);
    add_edge(&g, 1, 2, 1);
    add_edge(&g, 1, 3, 7);
    add_edge(&g, 2, 4, 3);
    add_edge(&g, 3, 4, 1);

    int dist[MAX_NODES];
    shortest_path_dag(&g, 0, dist);

    for (int i = 0; i < MAX_NODES; i++) {
        if (dist[i] == INT_MAX) {
            printf("Node %d: unreachable\n", i);
        } else {
            printf("Node %d: %d\n", i, dist[i]);
        }
    }
    return 0;
}

topological_sort(g, order);

Get nodes in order so all edges go forward

dist[start] = 0;

Set start node distance to zero

for (int i = 0; i < MAX_NODES; i++) { int u = order[i]; if (dist[u] != INT_MAX) { for (Edge* e = g->edges[u]; e != NULL; e = e->next) { int v = e->to; int w = e->weight; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } } }

Relax edges from each node in topological order to update shortest distances

Output

Node 0: 0

Node 1: 2

Node 2: 3

Node 3: 9

Node 4: 6

Complexity Analysis

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

Space: O(V + E) for storing graph edges and recursion stack in DFS

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

Edge Cases

Graph with no edges

Distances remain infinite except start node which is zero

DSA C

dist[start] = 0;

Single node graph

Distance to start node is zero, no other nodes

DSA C

dist[start] = 0;

Disconnected nodes

Unreachable nodes have distance INT_MAX and print as unreachable

DSA C

if (dist[i] == INT_MAX) { printf("Node %d: unreachable\n", i); }

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to relax edges efficiently without complex data structures.

Common Mistakes

Mistake: Not performing topological sort before relaxing edges
Fix: Always get topological order first to ensure correct relaxation sequence

Mistake: Initializing all distances to zero instead of infinity except start
Fix: Set start node distance to zero and others to a large number to represent unknown

Mistake: Relaxing edges in arbitrary order causing incorrect distances
Fix: Relax edges strictly in topological order to guarantee correctness

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 relax edges in an order where all dependencies are processed before a node.

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