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.