Shortest Path in Directed Acyclic Graph

Last Updated : 03 Feb, 2023

Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices.

For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.

We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.

Following figure is taken from this source. It shows step by step process of finding shortest paths.

TopologicalSort

TopologicalSort

Following is complete algorithm for finding shortest distances.

Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.

Create a topological order of all vertices.

Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)

Implementation:

C++

// C++ program to find single source shortest
// paths for Directed Acyclic Graphs
#include<iostream>
#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;
 
// Graph is represented using adjacency list. Every node
// of adjacency list contains vertex number of the vertex
// to which edge connects. It also 
// contains weight of the edge
class AdjListNode
{
    int v;
    int weight;
public:
    AdjListNode(int _v, int _w)  { v = _v;  weight = _w;}
    int getV()       {  return v;  }
    int getWeight()  {  return weight; }
};
 
// Class to represent a graph using adjacency
// list representation
class Graph
{
    int V;    // No. of vertices'
 
    // Pointer to an array containing adjacency lists
    list<AdjListNode> *adj;
 
    // A function used by shortestPath
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
    Graph(int V);   // Constructor
 
    // function to add an edge to graph
    void addEdge(int u, int v, int weight);
 
    // Finds shortest paths from given source vertex
    void shortestPath(int s);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<AdjListNode>[V];
}
 
void Graph::addEdge(int u, int v, int weight)
{
    AdjListNode node(v, weight);
    adj[u].push_back(node); // Add v to u's list
}
 
// A recursive function used by shortestPath. 
// See below link for details 
// https://www.geeksforgeeks.org/topological-sorting/
void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
{
    // Mark the current node as visited
    visited[v] = true;
 
    // Recur for all the vertices adjacent to this vertex
    list<AdjListNode>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    {
        AdjListNode node = *i;
        if (!visited[node.getV()])
            topologicalSortUtil(node.getV(), visited, Stack);
    }
 
    // Push current vertex to stack which stores topological sort
    Stack.push(v);
}
 
// The function to find shortest paths from given vertex.
// It uses recursive topologicalSortUtil() to get topological 
// sorting of given graph.
void Graph::shortestPath(int s)
{
    stack<int> Stack;
    int dist[V];
 
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Call the recursive helper function to store
    // Topological Sort starting from all vertices 
    // one by one
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            topologicalSortUtil(i, visited, Stack);
 
    // Initialize distances to all vertices as
    // infinite and distance to source as 0
    for (int i = 0; i < V; i++)
        dist[i] = INF;
    dist[s] = 0;
 
    // Process vertices in topological order
    while (Stack.empty() == false)
    {
        // Get the next vertex from topological order
        int u = Stack.top();
        Stack.pop();
 
        // Update distances of all adjacent vertices
        list<AdjListNode>::iterator i;
        if (dist[u] != INF)
        {
          for (i = adj[u].begin(); i != adj[u].end(); ++i)
             if (dist[i->getV()] > dist[u] + i->getWeight())
                dist[i->getV()] = dist[u] + i->getWeight();
        }
    }
 
    // Print the calculated shortest distances
    for (int i = 0; i < V; i++)
        (dist[i] == INF)? cout << "INF ": cout << dist[i] << " ";
}
 
// Driver program to test above functions
int main()
{
    // Create a graph given in the above diagram. 
    // Here vertex numbers are 0, 1, 2, 3, 4, 5 with 
    // following mappings: 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
    Graph g(6);
    g.addEdge(0, 1, 5);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 3, 6);
    g.addEdge(1, 2, 2);
    g.addEdge(2, 4, 4);
    g.addEdge(2, 5, 2);
    g.addEdge(2, 3, 7);
    g.addEdge(3, 4, -1);
    g.addEdge(4, 5, -2);
 
    int s = 1;
    cout << "Following are shortest distances from source " << s <<" n";
    g.shortestPath(s);
 
    return 0;
}

Java

// Java program to find single source shortest paths in Directed Acyclic Graphs
import java.io.*;
import java.util.*;
 
class ShortestPath
{
    static final int INF=Integer.MAX_VALUE;
    class AdjListNode
    {
        private int v;
        private int weight;
        AdjListNode(int _v, int _w) { v = _v;  weight = _w; }
        int getV() { return v; }
        int getWeight()  { return weight; }
    }
 
    // Class to represent graph as an adjacency list of
    // nodes of type AdjListNode
    class Graph
    {
        private int V;
        private LinkedList<AdjListNode>adj[];
        Graph(int v)
        {
            V=v;
            adj = new LinkedList[V];
            for (int i=0; i<v; ++i)
                adj[i] = new LinkedList<AdjListNode>();
        }
        void addEdge(int u, int v, int weight)
        {
            AdjListNode node = new AdjListNode(v,weight);
            adj[u].add(node);// Add v to u's list
        }
 
        // A recursive function used by shortestPath.
        // See below link for details
        void topologicalSortUtil(int v, Boolean visited[], Stack stack)
        {
            // Mark the current node as visited.
            visited[v] = true;
            Integer i;
 
            // Recur for all the vertices adjacent to this vertex
            Iterator<AdjListNode> it = adj[v].iterator();
            while (it.hasNext())
            {
                AdjListNode node =it.next();
                if (!visited[node.getV()])
                    topologicalSortUtil(node.getV(), visited, stack);
            }
            // Push current vertex to stack which stores result
            stack.push(new Integer(v));
        }
 
        // The function to find shortest paths from given vertex. It
        // uses recursive topologicalSortUtil() to get topological
        // sorting of given graph.
        void shortestPath(int s)
        {
            Stack stack = new Stack();
            int dist[] = new int[V];
 
            // Mark all the vertices as not visited
            Boolean visited[] = new Boolean[V];
            for (int i = 0; i < V; i++)
                visited[i] = false;
 
            // Call the recursive helper function to store Topological
            // Sort starting from all vertices one by one
            for (int i = 0; i < V; i++)
                if (visited[i] == false)
                    topologicalSortUtil(i, visited, stack);
 
            // Initialize distances to all vertices as infinite and
            // distance to source as 0
            for (int i = 0; i < V; i++)
                dist[i] = INF;
            dist[s] = 0;
 
            // Process vertices in topological order
            while (stack.empty() == false)
            {
                // Get the next vertex from topological order
                int u = (int)stack.pop();
 
                // Update distances of all adjacent vertices
                Iterator<AdjListNode> it;
                if (dist[u] != INF)
                {
                    it = adj[u].iterator();
                    while (it.hasNext())
                    {
                        AdjListNode i= it.next();
                        if (dist[i.getV()] > dist[u] + i.getWeight())
                            dist[i.getV()] = dist[u] + i.getWeight();
                    }
                }
            }
 
            // Print the calculated shortest distances
            for (int i = 0; i < V; i++)
            {
                if (dist[i] == INF)
                    System.out.print( "INF ");
                else
                    System.out.print( dist[i] + " ");
            }
        }
    }
 
    // Method to create a new graph instance through an object
    // of ShortestPath class.
    Graph newGraph(int number)
    {
        return new Graph(number);
    }
 
    public static void main(String args[])
    {
        // Create a graph given in the above diagram.  Here vertex
        // numbers are 0, 1, 2, 3, 4, 5 with following mappings:
        // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
        ShortestPath t = new ShortestPath();
        Graph g = t.newGraph(6);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);
 
        int s = 1;
        System.out.println("Following are shortest distances "+
                            "from source " + s );
        g.shortestPath(s);
    }
}
//This code is contributed by Aakash Hasija

Python3

# Python program to find single source shortest paths
# for Directed Acyclic Graphs Complexity :O(V+E)
from collections import defaultdict
 
# Graph is represented using adjacency list. Every
# node of adjacency list contains vertex number of
# the vertex to which edge connects. It also contains
# weight of the edge
class Graph:
    def __init__(self,vertices):
 
        self.V = vertices # No. of vertices
 
        # dictionary containing adjacency List
        self.graph = defaultdict(list)
 
    # function to add an edge to graph
    def addEdge(self,u,v,w):
        self.graph[u].append((v,w))
 
 
    # A recursive function used by shortestPath
    def topologicalSortUtil(self,v,visited,stack):
 
        # Mark the current node as visited.
        visited[v] = True
 
        # Recur for all the vertices adjacent to this vertex
        if v in self.graph.keys():
            for node,weight in self.graph[v]:
                if visited[node] == False:
                    self.topologicalSortUtil(node,visited,stack)
 
        # Push current vertex to stack which stores topological sort
        stack.append(v)
 
 
    ''' The function to find shortest paths from given vertex.
        It uses recursive topologicalSortUtil() to get topological
        sorting of given graph.'''
    def shortestPath(self, s):
 
        # Mark all the vertices as not visited
        visited = [False]*self.V
        stack =[]
 
        # Call the recursive helper function to store Topological
        # Sort starting from source vertices
        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(s,visited,stack)
 
        # Initialize distances to all vertices as infinite and
        # distance to source as 0
        dist = [float("Inf")] * (self.V)
        dist[s] = 0
 
        # Process vertices in topological order
        while stack:
 
            # Get the next vertex from topological order
            i = stack.pop()
 
            # Update distances of all adjacent vertices
            for node,weight in self.graph[i]:
                if dist[node] > dist[i] + weight:
                    dist[node] = dist[i] + weight
 
        # Print the calculated shortest distances
        for i in range(self.V):
            print (("%d" %dist[i]) if dist[i] != float("Inf") else  "Inf" ,end=" ")
 
 
g = Graph(6)
g.addEdge(0, 1, 5)
g.addEdge(0, 2, 3)
g.addEdge(1, 3, 6)
g.addEdge(1, 2, 2)
g.addEdge(2, 4, 4)
g.addEdge(2, 5, 2)
g.addEdge(2, 3, 7)
g.addEdge(3, 4, -1)
g.addEdge(4, 5, -2)
 
# source = 1
s = 1
 
print ("Following are shortest distances from source %d " % s)
g.shortestPath(s)
 
# This code is contributed by Neelam Yadav

C#

// C# program to find single source shortest
// paths in Directed Acyclic Graphs
using System;
using System.Collections.Generic;
 
public class ShortestPath
{
    static readonly int INF = int.MaxValue;
    class AdjListNode
    {
        public int v;
        public int weight;
        public AdjListNode(int _v, int _w) { v = _v; weight = _w; }
        public int getV() { return v; }
        public int getWeight() { return weight; }
    }
 
    // Class to represent graph as an adjacency list of
    // nodes of type AdjListNode
    class Graph
    {
        public int V;
        public List<AdjListNode>[]adj;
        public Graph(int v)
        {
            V = v;
            adj = new List<AdjListNode>[V];
            for (int i = 0; i < v; ++i)
                adj[i] = new List<AdjListNode>();
        }
        public void addEdge(int u, int v, int weight)
        {
            AdjListNode node = new AdjListNode(v,weight);
            adj[u].Add(node);// Add v to u's list
        }
 
        // A recursive function used by shortestPath.
        // See below link for details
        public void topologicalSortUtil(int v, Boolean []visited, 
                                        Stack<int> stack)
        {
            // Mark the current node as visited.
            visited[v] = true;
 
            // Recur for all the vertices adjacent to this vertex
            foreach(AdjListNode it in adj[v])
            {
                AdjListNode node = it;
                if (!visited[node.getV()])
                    topologicalSortUtil(node.getV(), visited, stack);
            }
             
            // Push current vertex to stack which stores result
            stack.Push(v);
        }
 
        // The function to find shortest paths from given vertex. It
        // uses recursive topologicalSortUtil() to get topological
        // sorting of given graph.
        public void shortestPath(int s)
        {
            Stack<int> stack = new Stack<int>();
            int []dist = new int[V];
 
            // Mark all the vertices as not visited
        Boolean []visited = new Boolean[V];
            for (int i = 0; i < V; i++)
                visited[i] = false;
 
            // Call the recursive helper function to store Topological
            // Sort starting from all vertices one by one
            for (int i = 0; i < V; i++)
                if (visited[i] == false)
                    topologicalSortUtil(i, visited, stack);
 
            // Initialize distances to all vertices as infinite and
            // distance to source as 0
            for (int i = 0; i < V; i++)
                dist[i] = INF;
            dist[s] = 0;
 
            // Process vertices in topological order
            while (stack.Count != 0)
            {
                // Get the next vertex from topological order
                int u = (int)stack.Pop();
 
                // Update distances of all adjacent vertices
                if (dist[u] != INF)
                {
                    foreach(AdjListNode it in adj[u]) 
                    {
                        AdjListNode i= it;
                        if (dist[i.getV()] > dist[u] + i.getWeight())
                            dist[i.getV()] = dist[u] + i.getWeight();
                    }
                }
            }
 
            // Print the calculated shortest distances
            for (int i = 0; i < V; i++)
            {
                if (dist[i] == INF)
                    Console.Write( "INF ");
                else
                    Console.Write( dist[i] + " ");
            }
        }
    }
 
    // Method to create a new graph instance through an object
    // of ShortestPath class.
    Graph newGraph(int number)
    {
        return new Graph(number);
    }
 
    // Driver code
    public static void Main(String []args)
    {
        // Create a graph given in the above diagram. Here vertex
        // numbers are 0, 1, 2, 3, 4, 5 with following mappings:
        // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
        ShortestPath t = new ShortestPath();
        Graph g = t.newGraph(6);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(2, 4, 4);
        g.addEdge(2, 5, 2);
        g.addEdge(2, 3, 7);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);
 
        int s = 1;
        Console.WriteLine("Following are shortest distances "+
                            "from source " + s );
        g.shortestPath(s);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

// Javascript program to find single source shortest
// paths for Directed Acyclic Graphs
 
      // program to implement stack data structure
      class stack {
        constructor() {
          this.items = [];
        }
 
        // add element to the stack
        push(element) {
          return this.items.push(element);
        }
 
        // remove element from the stack
        pop() {
          if (this.items.length > 0) {
            return this.items.pop();
          }
        }
 
        // view the last element
        top() {
          return this.items[this.items.length - 1];
        }
 
        // check if the stack is empty
        empty() {
          return this.items.length == 0;
        }
 
        // the size of the stack
        size() {
          return this.items.length;
        }
 
        // empty the stack
        clear() {
          this.items = [];
        }
      }
 
      let INF = Number.MAX_VALUE;
 
      // Graph is represented using adjacency list. Every node
      // of adjacency list contains vertex number of the vertex
      // to which edge connects. It also
      // contains weight of the edge
      class AdjListNode {
        constructor(_v, _w) {
          this.v = _v;
          this.weight = _w;
        }
        getV() {
          return this.v;
        }
        getWeight() {
          return this.weight;
        }
      }
 
      // Class to represent a graph using adjacency
      // list representation
      class Graph {
        // Constructor
        constructor(V) {
          this.V = V; // No. of vertices'
          // Pointer to an array containing adjacency lists
          this.adj = Array.from(Array(V), () => new Array());
        }
 
        // A function used by shortestPath
        topologicalSortUtil(v, visited, Stack) {
          // Mark the current node as visited
          visited[v] = true;
 
          // Recur for all the vertices adjacent to this vertex
 
          for (let j in this.adj[v]) {
            let i = this.adj[v][j];
            let node = i;
            if (!visited[node.getV()])
              this.topologicalSortUtil(node.getV(), visited, Stack);
          }
 
          // Push current vertex to stack which stores topological
          // sort
          Stack.push(v);
        }
 
        // function to add an edge to graph
        addEdge(u, v, weight) {
          let node = new AdjListNode(v, weight);
          this.adj[u].push(node); // Add v to u's list
        }
 
        // The function to find shortest paths from given vertex.
        // It uses recursive topologicalSortUtil() to get topological
        // sorting of given graph.
        shortestPath(s) {
          let Stack = new stack();
          let dist = new Array(this.V);
 
          // Mark all the vertices as not visited
          let visited = new Array(this.V);
          for (let i = 0; i < this.V; i++) {
            visited[i] = false;
          }
 
          // Call the recursive helper function to store Topological
          // Sort starting from all vertices one by one
          for (let i = 0; i < this.V; i++)
            if (visited[i] == false)
              this.topologicalSortUtil(i, visited, Stack);
 
          // Initialize distances to all vertices as infinite and
          // distance to source as 0
          for (let i = 0; i < this.V; i++) dist[i] = INF;
          dist[s] = 0;
 
          // Process vertices in topological order
          while (Stack.empty() == false) {
            // Get the next vertex from topological order
            let u = Stack.top();
            Stack.pop();
 
            // Update distances of all adjacent vertices
 
            if (dist[u] != INF) {
              for (let j in this.adj[u]) {
                let i = this.adj[u][j];
                if (dist[i.getV()] > dist[u] + i.getWeight())
                  dist[i.getV()] = dist[u] + i.getWeight();
              }
            }
          }
 
          // Print the calculated shortest distances
          for (let i = 0; i < this.V; i++)
            dist[i] == INF ? console.log("INF ") : console.log(dist[i] + " ");
        }
      }
 
      // Driver program to test above functions
 
      // Create a graph given in the above diagram.
      // Here vertex numbers are 0, 1, 2, 3, 4, 5 with
      // following mappings: 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
      let g = new Graph(6);
      g.addEdge(0, 1, 5);
      g.addEdge(0, 2, 3);
      g.addEdge(1, 3, 6);
      g.addEdge(1, 2, 2);
      g.addEdge(2, 4, 4);
      g.addEdge(2, 5, 2);
      g.addEdge(2, 3, 7);
      g.addEdge(3, 4, -1);
      g.addEdge(4, 5, -2);
 
      let s = 1;
      console.log("Following are shortest distances from source " + s);
      g.shortestPath(s);
       
      // This code is contributed by satwiksuman.

Output

Following are shortest distances from source 1 nINF 0 2 6 5 3

Time Complexity: Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).

Auxiliary Space : O(V+E)

GeeksforGeeks

Improve

Previous Article

Johnson's algorithm for All-pairs shortest paths

Multistage Graph (Shortest Path)

Similar Reads

Longest path in a directed Acyclic graph | Dynamic Programming

Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph.Note: Length of a directed path is the number of edges in it. Examples: Input: N = 4, M = 5 Output: 3 The directed path 1->3->2->4 Input: N = 5, M = 8 Output: 3 Simple Approach: A naive approach is to calculate the len

Longest Path in a Directed Acyclic Graph | Set 2

Given a Weighted Directed Acyclic Graph (DAG) and a source vertex in it, find the longest distances from source vertex to all other vertices in the given graph. We have already discussed how we can find Longest Path in Directed Acyclic Graph(DAG) in Set 1. In this post, we will discuss another interesting solution to find longest path of DAG that u

Longest Path in a Directed Acyclic Graph

Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph. The longest path problem for a general graph is not as easy as the shortest path problem because the longest path problem doesn’t have optimal substructure property. In fact, the Longest Path problem

What is Directed Graph? | Directed Graph meaning

A directed graph is defined as a type of graph where the edges have a direction associated with them. Characteristics of Directed Graph Directed graphs have several characteristics that make them different from undirected graphs. Here are some key characteristics of directed graphs: Directed edges: In a directed graph, edges have a direction associ

Assign directions to edges so that the directed graph remains acyclic

Given a graph with both directed and undirected edges. It is given that the directed edges don't form cycle. How to assign directions to undirected edges so that the graph (with all directed edges) remains acyclic even after the assignment? For example, in the below graph, blue edges don't have directions. We strongly recommend to minimize your bro

Number of paths from source to destination in a directed acyclic graph

Given a Directed Acyclic Graph with n vertices and m edges. The task is to find the number of different paths that exist from a source vertex to destination vertex. Examples: Input: source = 0, destination = 4 Output: 3 Explanation: 0 -> 2 -> 3 -> 4 0 -> 3 -> 4 0 -> 4 Input: source = 0, destination = 1 Output: 1 Explanation: There

Maximum difference between node and its ancestor in a Directed Acyclic Graph ( DAG )

Given a 2D array Edges[][], representing a directed edge between the pair of nodes in a Directed Acyclic Connected Graph consisting of N nodes valued from [1, N] and an array arr[] representing weights of each node, the task is to find the maximum absolute difference between the weights of any node and any of its ancestors. Examples: Input: N = 5,

Count nodes with prime weight in a Directed Acyclic Graph

Given a directed acyclic graph (DAG) with N nodes with integer representations 0 to N-1 and an integer array arr[], where arr[i] is the parent of node i. The root of the DAG is node i if arr[i] is 0. The weight of a node is calculated as the sum of the node's value and the number of parent nodes it has, the task is to determine the number of nodes,

Introduction to Directed Acyclic Graph

A Directed Acyclic Graph, often abbreviated as DAG, is a fundamental concept in graph theory. DAGs are used to show how things are related or depend on each other in a clear and organized way. In this article, we are going to learn about Directed Acyclic Graph, its properties, and application in real life. What is Directed Acyclic Graph?A Directed

All Topological Sorts of a Directed Acyclic Graph

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. Given a DAG, print all topological sorts of the graph. For example, consider the below graph. All topological

Article Tags :

Practice Tags :