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.