ProgramGuru

Shortest Path in DAG using Topological Sort

Problem and examples

Given a Directed Acyclic Graph (DAG) with n vertices and weighted edges, find the shortest path from a given source node to all other nodes.

For this problem, we assume that the source node is always node 0. The graph is represented using an edge list where each edge has a weight. Your task is to compute the shortest distances from the source to all other nodes using topological sorting.

Nodes Edges Output Description
6 [[0,1,2],[0,4,1],[1,2,3],[4,2,2],[2,3,6],[4,5,4],[5,3,1]] [0,2,3,6,1,5] Shortest paths from node 0 using topological order and edge relaxation
3 [[0,1,5],[1,2,3]] [0,5,8] Path 0 → 1 → 2 accumulates weight
4 [[0,1,1],[0,2,4],[1,3,2],[2,3,1]] [0,1,4,3] Shortest path from 0 to 3 is via node 2
1 [] [0] Single node, no edges
3 [[1,2,1]] [0, ∞, ∞] No outgoing edges from source 0

How it works

Understanding the Problem

We are given a Directed Acyclic Graph (DAG) and a source node. Our goal is to find the shortest path from this source to all other nodes in the graph.

Unlike general graphs where we might use Dijkstra’s algorithm, here we can take advantage of the acyclic nature of the graph. Since there are no cycles, a topological order of nodes exists. In this order, for every directed edge u → v, node u comes before v. This means we can process each node and update distances of its neighbors in a single pass, efficiently solving the problem.

Step-by-Step Solution with Example

Step 1: Represent the Graph

Suppose we are given the following edge list for a graph with 6 nodes (0 to 5):


edges = [
  (0, 1, 2),
  (0, 4, 1),
  (1, 2, 3),
  (4, 2, 2),
  (2, 3, 6),
  (4, 5, 4),
  (5, 3, 1)
]

Each tuple (u, v, w) represents a directed edge from u to v with weight w. We first convert this into an adjacency list for easier processing.

Step 2: Topological Sort

We perform a topological sort on the DAG. This gives us an order in which we can safely process the nodes, ensuring that all prerequisites for a node are processed before it.

For the above graph, one possible topological order is: [0, 1, 4, 5, 2, 3].

Step 3: Initialize Distances

We set up an array dist to keep track of the shortest distance from the source node to every other node. Initially, all distances are set to infinity except for the source (let's say source is node 0), which is set to 0:


dist = [0, ∞, ∞, ∞, ∞, ∞]

Step 4: Process Nodes in Topological Order

Now we traverse the nodes in topological order. For each node, we look at its outgoing edges and try to "relax" them. Relaxing means: if the current known distance to the neighbor is greater than the distance to the current node plus the edge weight, we update it.

Let's walk through it:

  • From node 0 → 1 (weight 2): dist[1] = min(∞, 0+2) = 2
  • From node 0 → 4 (weight 1): dist[4] = min(∞, 0+1) = 1
  • From node 1 → 2 (weight 3): dist[2] = min(∞, 2+3) = 5
  • From node 4 → 2 (weight 2): dist[2] = min(5, 1+2) = 3
  • From node 4 → 5 (weight 4): dist[5] = min(∞, 1+4) = 5
  • From node 5 → 3 (weight 1): dist[3] = min(∞, 5+1) = 6
  • From node 2 → 3 (weight 6): dist[3] = min(6, 3+6) = 6 (no change)

Final dist array: [0, 2, 3, 6, 1, 5]

Edge Cases

  • Disconnected Nodes: If a node is not reachable from the source, its distance will remain ∞. Always check for such cases before interpreting the results.
  • Multiple Valid Topological Orders: The topological sort is not unique. As long as it's a valid topological order, the final distances will be the same.
  • Zero-weight Edges: Edges with weight 0 are still valid and can affect shortest paths. Our relaxation logic should include them.
  • Negative Weights: Since we’re in a DAG, negative edge weights are safe and won’t create cycles. The algorithm works fine with them.

Finally

Using topological sort for shortest path in DAGs is optimal and elegant. It avoids unnecessary overhead of priority queues or repeated visits. Understanding how topological order guarantees that each node is processed only after all of its dependencies is the key to this approach.

Just remember: this method only works for DAGs. If your graph has cycles, you must use other algorithms like Dijkstra or Bellman-Ford depending on the context.

  1. Construct an adjacency list from the given edges.
  2. Perform a topological sort of the DAG using DFS.
  3. Initialize a distance array with Infinity for all nodes, except the source (node 0) which is set to 0.
  4. Iterate through each node in topological order:
    1. For each neighbor v of the current node u, update dist[v] = min(dist[v], dist[u] + weight)
  5. Return the final distance array. Nodes unreachable from source will retain Infinity.

Implementation and efficiency

C implementation

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

#define MAX 100

typedef struct {
    int u, v, w;
} Edge;

int adj[MAX][MAX], indegree[MAX], stack[MAX], top = -1;
int dist[MAX];

void topoSortUtil(int v, int visited[], int n) {
    visited[v] = 1;
    for (int i = 0; i < n; i++) {
        if (adj[v][i] != 0 && !visited[i]) {
            topoSortUtil(i, visited, n);
        }
    }
    stack[++top] = v;
}

void shortestPathDAG(int n) {
    int visited[MAX] = {0};
    for (int i = 0; i < n; i++) {
        if (!visited[i]) topoSortUtil(i, visited, n);
    }

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

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

    printf("Shortest distances from node 0:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
}

int main() {
    int n = 6;
    int edges[][3] = {{0,1,2},{0,4,1},{1,2,3},{4,2,2},{2,3,6},{4,5,4},{5,3,1}};
    int m = sizeof(edges)/sizeof(edges[0]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            adj[i][j] = 0;

    for (int i = 0; i < m; i++) {
        adj[edges[i][0]][edges[i][1]] = edges[i][2];
    }

    shortestPathDAG(n);
    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <stack>
#include <limits>
using namespace std;

void topoSort(int node, vector<vector<pair<int,int>>>& adj, vector<bool>& visited, stack<int>& st) {
    visited[node] = true;
    for (auto& [v, w] : adj[node]) {
        if (!visited[v]) {
            topoSort(v, adj, visited, st);
        }
    }
    st.push(node);
}

void shortestPathDAG(int n, vector<tuple<int,int,int>>& edges) {
    vector<vector<pair<int,int>>> adj(n);
    for (auto& [u, v, w] : edges) {
        adj[u].emplace_back(v, w);
    }
    
    vector<bool> visited(n, false);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) topoSort(i, adj, visited, st);
    }

    vector<int> dist(n, numeric_limits<int>::max());
    dist[0] = 0;

    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (dist[u] != numeric_limits<int>::max()) {
            for (auto& [v, w] : adj[u]) {
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
            }
        }
    }

    cout << "Shortest distances from node 0:\n";
    for (int d : dist) cout << d << " ";
    cout << endl;
}

int main() {
    int n = 6;
    vector<tuple<int,int,int>> edges = {{0,1,2},{0,4,1},{1,2,3},{4,2,2},{2,3,6},{4,5,4},{5,3,1}};
    shortestPathDAG(n, edges);
    return 0;
}

Python implementation

from collections import defaultdict

def shortest_path_dag(n, edges):
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append((v, w))

    visited = [False] * n
    stack = []

    def topo_sort(u):
        visited[u] = True
        for v, _ in adj[u]:
            if not visited[v]:
                topo_sort(v)
        stack.append(u)

    for i in range(n):
        if not visited[i]:
            topo_sort(i)

    dist = [float('inf')] * n
    dist[0] = 0

    while stack:
        u = stack.pop()
        if dist[u] != float('inf'):
            for v, w in adj[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

    print("Shortest distances from node 0:", dist)

shortest_path_dag(6, [(0,1,2),(0,4,1),(1,2,3),(4,2,2),(2,3,6),(4,5,4),(5,3,1)])

Java implementation

import java.util.*;

public class ShortestPathDAG {
    static void topoSort(int u, List<List<int[]>> adj, boolean[] visited, Stack<Integer> stack) {
        visited[u] = true;
        for (int[] edge : adj.get(u)) {
            if (!visited[edge[0]]) {
                topoSort(edge[0], adj, visited, stack);
            }
        }
        stack.push(u);
    }

    static void shortestPath(int n, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }

        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) topoSort(i, adj, visited, stack);
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (dist[u] != Integer.MAX_VALUE) {
                for (int[] edge : adj.get(u)) {
                    if (dist[u] + edge[1] < dist[edge[0]]) {
                        dist[edge[0]] = dist[u] + edge[1];
                    }
                }
            }
        }

        System.out.println("Shortest distances from node 0:");
        for (int d : dist) System.out.print(d + " ");
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1,2},{0,4,1},{1,2,3},{4,2,2},{2,3,6},{4,5,4},{5,3,1}};
        shortestPath(6, edges);
    }
}

JavaScript implementation

function shortestPathDAG(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    adj[u].push([v, w]);
  }

  const visited = new Array(n).fill(false);
  const stack = [];

  function topoSort(node) {
    visited[node] = true;
    for (const [neighbor] of adj[node]) {
      if (!visited[neighbor]) {
        topoSort(neighbor);
      }
    }
    stack.push(node);
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) topoSort(i);
  }

  const dist = new Array(n).fill(Infinity);
  dist[0] = 0;

  while (stack.length) {
    const node = stack.pop();
    if (dist[node] !== Infinity) {
      for (const [neighbor, weight] of adj[node]) {
        if (dist[node] + weight < dist[neighbor]) {
          dist[neighbor] = dist[node] + weight;
        }
      }
    }
  }

  console.log("Shortest Path:", dist);
}

shortestPathDAG(6, [[0,1,2],[0,4,1],[1,2,3],[4,2,2],[2,3,6],[4,5,4],[5,3,1]]);

Go implementation

package main

import (
	"fmt"
	"math"
)

type Edge struct {
	u, v, w int
}

func topoSort(u int, adj [][][2]int, visited []bool, stack *[]int) {
	visited[u] = true
	for _, edge := range adj[u] {
		if !visited[edge[0]] {
			topoSort(edge[0], adj, visited, stack)
		}
	}
	*stack = append(*stack, u)
}

func shortestPathDAG(n int, edges []Edge) {
	adj := make([][][2]int, n)
	for _, e := range edges {
		adj[e.u] = append(adj[e.u], [2]int{e.v, e.w})
	}

	visited := make([]bool, n)
	stack := []int{}
	for i := 0; i < n; i++ {
		if !visited[i] {
			topoSort(i, adj, visited, &stack)
		}
	}

	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[0] = 0

	for i := len(stack) - 1; i >= 0; i-- {
		u := stack[i]
		if dist[u] != math.MaxInt32 {
			for _, e := range adj[u] {
				if dist[u]+e[1] < dist[e[0]] {
					dist[e[0]] = dist[u] + e[1]
				}
			}
		}
	}

	fmt.Println("Shortest distances from node 0:", dist)
}

func main() {
	edges := []Edge{{0,1,2},{0,4,1},{1,2,3},{4,2,2},{2,3,6},{4,5,4},{5,3,1}}
	shortestPathDAG(6, edges)
}

Rust implementation

use std::collections::VecDeque;

fn shortest_path_dag(n: usize, edges: &[(usize, usize, i32)]) {
    let mut adj = vec![vec![]; n];
    for &(u, v, w) in edges {
        adj[u].push((v, w));
    }

    let mut visited = vec![false; n];
    let mut stack = Vec::new();

    fn dfs(u: usize, adj: &Vec<Vec<(usize, i32)>>, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
        visited[u] = true;
        for &(v, _) in &adj[u] {
            if !visited[v] {
                dfs(v, adj, visited, stack);
            }
        }
        stack.push(u);
    }

    for i in 0..n {
        if !visited[i] {
            dfs(i, &adj, &mut visited, &mut stack);
        }
    }

    let mut dist = vec![i32::MAX; n];
    dist[0] = 0;

    while let Some(u) = stack.pop() {
        if dist[u] != i32::MAX {
            for &(v, w) in &adj[u] {
                if dist[u] + w < dist[v] {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

    println!("Shortest distances from node 0: {:?}", dist);
}

fn main() {
    let edges = [(0,1,2),(0,4,1),(1,2,3),(4,2,2),(2,3,6),(4,5,4),(5,3,1)];
    shortest_path_dag(6, &edges);
}

Kotlin implementation

fun shortestPathDAG(n: Int, edges: List<Triple<Int, Int, Int>>) {
    val adj = List(n) { mutableListOf<Pair<Int, Int>>() }
    for ((u, v, w) in edges) adj[u].add(Pair(v, w))

    val visited = BooleanArray(n)
    val stack = mutableListOf<Int>()

    fun dfs(u: Int) {
        visited[u] = true
        for ((v, _) in adj[u]) {
            if (!visited[v]) dfs(v)
        }
        stack.add(u)
    }

    for (i in 0 until n) if (!visited[i]) dfs(i)

    val dist = IntArray(n) { Int.MAX_VALUE }
    dist[0] = 0

    for (i in stack.reversed()) {
        if (dist[i] != Int.MAX_VALUE) {
            for ((v, w) in adj[i]) {
                if (dist[i] + w < dist[v]) dist[v] = dist[i] + w
            }
        }
    }

    println("Shortest distances from node 0: ${dist.joinToString()}")
}

fun main() {
    val edges = listOf(
        Triple(0,1,2), Triple(0,4,1), Triple(1,2,3),
        Triple(4,2,2), Triple(2,3,6), Triple(4,5,4), Triple(5,3,1)
    )
    shortestPathDAG(6, edges)
}

Swift implementation

func shortestPathDAG(n: Int, edges: [(Int, Int, Int)]) {
    var adj = Array(repeating: [(Int, Int)](), count: n)
    for (u, v, w) in edges { adj[u].append((v, w)) }

    var visited = Array(repeating: false, count: n)
    var stack = [Int]()

    func dfs(_ u: Int) {
        visited[u] = true
        for (v, _) in adj[u] where !visited[v] {
            dfs(v)
        }
        stack.append(u)
    }

    for i in 0..<n where !visited[i] { dfs(i) }

    var dist = Array(repeating: Int.max, count: n)
    dist[0] = 0

    while !stack.isEmpty {
        let u = stack.removeLast()
        if dist[u] != Int.max {
            for (v, w) in adj[u] {
                if dist[u] + w < dist[v] {
                    dist[v] = dist[u] + w
                }
            }
        }
    }
    print("Shortest distances from node 0:", dist)
}

let edges = [(0,1,2),(0,4,1),(1,2,3),(4,2,2),(2,3,6),(4,5,4),(5,3,1)]
shortestPathDAG(n: 6, edges: edges)

TypeScript implementation

function shortestPathDAG(n: number, edges: [number, number, number][]): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) {
    adj[u].push([v, w]);
  }

  const visited = new Array(n).fill(false);
  const stack: number[] = [];

  function topoSort(node: number): void {
    visited[node] = true;
    for (const [neighbor] of adj[node]) {
      if (!visited[neighbor]) topoSort(neighbor);
    }
    stack.push(node);
  }

  for (let i = 0; i < n; i++) if (!visited[i]) topoSort(i);

  const dist = new Array(n).fill(Infinity);
  dist[0] = 0;

  while (stack.length) {
    const node = stack.pop()!;
    if (dist[node] !== Infinity) {
      for (const [neighbor, weight] of adj[node]) {
        if (dist[node] + weight < dist[neighbor]) {
          dist[neighbor] = dist[node] + weight;
        }
      }
    }
  }

  return dist;
}

console.log("Shortest Path:", shortestPathDAG(6, [[0,1,2],[0,4,1],[1,2,3],[4,2,2],[2,3,6],[4,5,4],[5,3,1]]));