In graph theory, identifying the shortest path from a single vertex to all others is essential. The Bellman-Ford algorithm accomplishes this in O(V×E) time. However, for Directed Acyclic Graphs (DAGs), topological sorting offers a more efficient approach.

Before delving deeper, let’s understand what a Directed Acyclic Graph (DAG) is. Essentially, it’s a directed graph free of cycles, as illustrated in the upcoming image.

This article will delve into how to find the shortest paths in a weighted DAG. Understanding DAGs, which are directed graphs without cycles, is crucial for grasping complex network structures in computer science.

## Intuition

For general weighted graphs, we can use the Bellman Ford algorithm to find single source shortest paths in $O(V\times E)$ time.

But here we have been given a special property of the graph that it is a `Directed Acyclic Graph`

so we will utilize this property to perform our task in an efficient way. The idea is to use Topological Sorting.

Once we have the topological order of the given DAG, we will process the vertices in the same order. Here, processing a vertex means, updating distances of its adjacent vertices using the distance of the current vertex from `start`

.

## Algorithm

### Topological Sort

- Create a Stack (say
`st`

) which will be used to store the topological ordering. - Create a boolean array (say
`visited`

), it will be used to mark the vertices which have been visited. - For each unvisited vertex (say
`node`

) from 0 to V-1 call a recursive helper function which will do the following:- Mark
`node`

as visited. - For each adjacent vertex of
`node`

call the recursive function. - Push
`node`

in`st`

.

- Mark

### Shortest Path

- Find topological ordering of the given graph
- Create an array (say
`dist`

) of size`V`

, and initialize all its entries with a very large number (say`INF`

). - Traverse over all the vertices in topological order and for each vertex
`u`

, check the following conditon for all the adjancent vetex`v`

of`u`

If (`dist[v]`

>`dist[u]`

+ weightOfEdge(`u`

$\rightarrow$`v`

)) then`dist[v]`

=`dist[u]`

+ weightOfEdge(`u`

$\rightarrow$`v`

)

## Example

Consider the below given Directed acyclic graph and let’s say we need to find the shortest distance of all vertices from vertex `0`

.

As per the algorithm discussed in the previous section, we will first find the topological sorting of this graph.`topo = [1, 0, 2, 4, 3]`

If you are finding any difficulty in finding the topological order please have a look at Topological Sort.

Now we will create an array `dist`

of size V (here V=5) all entries of which will be initialized with `INF`

. Then assign `dist[start]=0`

.`dist = [0, INF, INF, INF, INF]`

The next step is to traverse vertices in topological order.

`topo[0]=1`

The adjacent vertices of`1`

are`0, 2, and 3`

. So we will check the following:- If
**dist[0] > dist[1] + weightOfEdge(1 $\rightarrow$ 0)**, putting their values will give`0 > INF + 3`

, which evaluates to false. - If
**dist[2] > dist[1] + wightOfEdge(1 $\rightarrow$ 2)**, putting their values will give`INF > INF + 2`

, which evaluates to false. - If
**dist[3] > dist[1] + wightOfEdge(1$\rightarrow$ 3)**, putting ther values will give`INF > INF + 5`

, which evaluates to false.

After these steps`dist`

array will look like`dist = [0, INF, INF, INF, INF]`

- If
`topo[1]=0`

The adjacent vertex of`0 is 2`

. So we will check the following:- If
**dist[2] > dist[0] + weightOfEdge(0 $\rightarrow$ 2)**putting their values will give`INF > 0 + 4`

, which evaluates to true hence we will assign 4 to`dist[2]`

.

After this step`dist`

array will look like`dist = [0, INF, 4, INF, INF]`

- If
`topo[2]=2`

The adjacent vertices of 2 are 3 and 4. So we will check the following:- If
**dist[3] > dist[2] + weightOfEdge(2 $\rightarrow$ 3)**, putting their values will give`INF > 4 + (-3)`

, which evaluates to true hence we will assign 1 to`dist[3`

]. - If
**dist[4] > dist[2] + weightOfEdge(2 $\rightarrow$ 4)**, putting their values will give`INF > 4 + 2`

, which evaluates to true hence we will assign 6 to`dist[4]`

.

After these steps`dist`

array will look like`dist = [0, INF, 4, 1, 6]`

- If
`topo[3]=4`

The adjacent vertex of 4 is 3. So we will check the following:- If
**dist[3] > dist[4] + weightOfEdge(4 $\rightarrow$ 3)**putting their values will give`1 > 6 + 2`

, which evaluates to false.

- If
`topo[4]=3`

There are no adjancet vertices to 3 hence we will not do anything.

Finally the dist array will be `dist=[0, INF, 4, 1 ,6]`

.

## Implementation

As discussed in the algorithm section we will be having two functions i.e. `ShortestPath`

and `TopologicalSort`

.

1. **ShortestPath –**

It will take `src`

as an argument that represents the start/source vertex. We will declare an integer array `dist`

of size `V`

all of its entries will be initialized with a very large number and `dist[src]`

will be `0`

.

Then we will iterate over all vertices to find the topological ordering by calling the `TopologicalSort`

function, which will store the order in a stack (say `st`

).

Now we will iterate while `st`

is not empty and each time we will pop an element from `st`

(say `u`

), then we will check if `dist[u]!=INF`

which means if `u`

is reachable from `src`

. If the conditio is found true then we iterate for all adjacent vertices of `u`

and check –

$$\text{dist[u’s Adjacent]}>(\text{dist[u]}+\text{Weight of Edge }(\text{u}\rightarrow\text{u’s Adjacent}))$$

If the condition is found true, then we will assign RHS to LHS.

At last, we will print the `dist`

array, where `dist[i]`

denotes the shortest distance of `i`

from `src`

.

2. **TopologicalSort –**

It is just like standard implementation of topological sorting, which takes three arguments Viz. `v`

, `visited`

array and Stack `st`

.

Firstly we mark `v`

as `visited`

, then we will traverse all adjacent nodes of v, call the same `TopologicalSort`

recursively if an adjacent node is not visited.

At last, we will push `v`

into Stack `st`

.

### Pseudocode

```
// Function to find topological Sort which is always possible
// as the given graph is a DAG.
function TopologicalSort(v, visited[], Stack st):
// Mark v as visited.
visited[v]=true
// Iterate for all the adjacent nodes of v.
For node in adj[v]:
// If any adjacent node to v is not
// visited, call topologicalSort function on it.
If visited[node.vertex] = False:
TopologicalSort(node.vertex, visited, st)
// Push v into Stack
st.push(v)
end function
// Function to compute the shortest path
// to all other vertices starting from src.
function ShortestPath(src){
// Declare a Stack (st) which is used to find
// the topological sort of the given DAG.
Stack st
// Declare a dist array where dist[i] denotes
// shortest distance of src from i.
// Initialize all it's entries with INF and
// dist[src] with 0.
dist[V]
For i=0 To i=V-1:
dist[i]=INF
dist[src]=0
// Create boolean visited array to keep track
// of visited elements.
visited[V]
// Iterate for all the V vertices.
For i=0 To i=V-1:
// If 'i' found to unvisited call
// topoplogicalSort from there.
If visited[i] = False:
TopologicalSort(i,visited,st)
// Iterate till the stack is not empty.
While st is not Empty:
// Pop element from stack and store it in u.
u=st.pop
// If shortest distance from src to u is
// not infinity i.e. it is reachable.
If dist[u]!=INF:
// Iterate for all the adjacent vertices
// of u.
For node in adj.get[u]:
// If distance of src->v is greater than
// distance of src->u + u->v then update
// the value as shown.
If dist[node.v] > dist[u] + node.weight:
dist[node.v] = dist[u] + node.weight
// Print the distances.
For i=0 To i=V-1:
If dist[i] == INF:
Print("INF ")
Else:
Print(dist[i])
end function
```

### C/C++ Implementation

```
// C++ program to find single source shortest paths
// in a Directed Acyclic Graph (DAG).
#include<bits/stdc++.h>
using namespace std;
// V represents number of Vertices, present
// in the given DAG.
int V;
// INF means infinity, which is taken
// as largest possible value of 32-bit integer.
int INF=INT_MAX;
// Node class
class Node{
public:
// v is the vertex,
// and wt is the weight.
int v;
int wt;
Node(int _v,int _wt){
v=_v;
wt=_wt;
}
};
vector<vector<Node>> adj;
// Function to add edge u->v of weigth wt.
void addEdge(int u,int v,int wt){
adj[u].push_back(Node(v,wt));
}
// Adjacency list.
// Function to find topological Sort which is always possible
// as the given graph is a DAG.
void topologicalSort(int v, bool *visited,
stack<int> &st){
// Marking v as visited.
visited[v]=true;
// Iterating for all the adjacent nodes of v.
for(Node node:adj[v]){
// If any adjacent node to v is not
// visited, call topologicalSort function on it.
if(!visited[node.v]){
topologicalSort(node.v, visited, st);
}
}
// Push v into Stack
st.push(v);
}
// Function to compute the shortest path
// to all other vertices starting from src.
void shortestPath(int src){
// Declare a Stack (st) which is used to find
// the topological sort of the given DAG.
stack<int> st;
// Declare a dist array where dist[i] denotes
// shortest distance of src from i.
// Initialize all it's entries with INF and
// dist[src] with 0.
int dist[V];
for(int i=0;i<V;i++)
dist[i]=INF;
dist[src]=0;
// Create boolean visited array to keep track
// of visited elements.
bool visited[V];
for(int i=0;i<V;i++)
visited[i]=false;
// Iterate for all the V vertices.
for(int i=0;i<V;i++){
// If 'i' found to unvisited call
// topoplogicalSort from there.
if(!visited[i]){
topologicalSort(i,visited,st);
}
}
// Iterate till the stack is not empty.
while(!st.empty()){
// Pop element from stack and store it in u.
int u=st.top();
st.pop();
// If shortest distance from src to u is
// not infinity i.e. it is reachable.
if(dist[u]!=INF){
// Iterate for all the adjacent vertices
// of u.
for(Node node:adj[u]){
// If distance of src->v is greater than
// distance of src->u + u->v then update
// the value as shown.
if(dist[node.v]>dist[u]+node.wt)
dist[node.v]=dist[u]+node.wt;
}
}
}
// Print the distances.
for(int i=0;i<V;i++){
if(dist[i]==INF)
cout<<"INF ";
else
cout<<dist[i]<<" ";
}
}
// Main function
int main(){
V=6;
// Initialize Adjacency List.
// adj=new ArrayList<>();
for(int i=0;i<V;i++)
adj.push_back(vector<Node>());
// Add edges.
addEdge(0, 2, 4);
addEdge(1, 0, 3);
addEdge(2, 3,-3);
addEdge(2, 4, 2);
addEdge(1, 2, 2);
addEdge(1, 3, 5);
addEdge(4, 3, 2);
// Find the shortest path from a
// vertex (here 0).
shortestPath(0);
return 0;
}
```

### Java Implementation

```
// Java program to find single source shortest paths
// in a Directed Acyclic Graph (DAG).
import java.util.*;
public class Main
{
// V represents number of Vertices, present
// in the given DAG.
static int V;
// INF means infinity, which is taken
// as largest possible value of 32-bit integer.
static final int INF=Integer.MAX_VALUE;
// Node class
static class Node{
// v is the vertex,
// and wt is the weight.
int v;
int wt;
Node(int v,int wt){
this.v=v;
this.wt=wt;
}
}
// Function to add edge u->v of weigth wt.
static void addEdge(int u,int v,int wt){
adj.get(u).add(new Node(v,wt));
}
// Adjacency list.
static List<List<Node>> adj;
// Function to find topological Sort which is always possible
// as the given graph is a DAG.
static void topologicalSort(int v, boolean visited[],
Stack<Integer> st){
// Marking v as visited.
visited[v]=true;
// Iterating for all the adjacent nodes of v.
for(Node node:adj.get(v)){
// If any adjacent node to v is not
// visited, call topologicalSort function on it.
if(!visited[node.v]){
topologicalSort(node.v, visited, st);
}
}
// Push v into Stack
st.push(v);
}
// Function to compute the shortest path
// to all other vertices starting from src.
static void shortestPath(int src){
// Declare a Stack (st) which is used to find
// the topological sort of the given DAG.
Stack<Integer> st=new Stack<>();
// Declare a dist array where dist[i] denotes
// shortest distance of src from i.
// Initialize all it's entries with INF and
// dist[src] with 0.
int dist[]=new int[V];
Arrays.fill(dist,INF);
dist[src]=0;
// Create boolean visited array to keep track
// of visited elements.
boolean visited[]=new boolean[V];
// Iterate for all the V vertices.
for(int i=0;i<V;i++){
// If 'i' found to unvisited call
// topoplogicalSort from there.
if(!visited[i]){
topologicalSort(i,visited,st);
}
}
// Iterate till the stack is not empty.
while(!st.isEmpty()){
// Pop element from stack and store it in u.
int u=st.pop();
// If shortest distance from src to u is
// not infinity i.e. it is reachable.
if(dist[u]!=INF){
// Iterate for all the adjacent vertices
// of u.
for(Node node:adj.get(u)){
// If distance of src->v is greater than
// distance of src->u + u->v then update
// the value as shown.
if(dist[node.v]>dist[u]+node.wt)
dist[node.v]=dist[u]+node.wt;
}
}
}
// Print the distances.
for(int i=0;i<V;i++){
if(dist[i]==INF)
System.out.print("INF ");
else
System.out.print(dist[i]+" ");
}
}
// Main function
public static void main(String args[])
{
V=6;
// Initialize Adjacency List.
adj=new ArrayList<>();
for(int i=0;i<V;i++)
adj.add(new ArrayList<Node>());
// Add edges.
addEdge(0, 2, 4);
addEdge(1, 0, 3);
addEdge(2, 3,-3);
addEdge(2, 4, 2);
addEdge(1, 2, 2);
addEdge(1, 3, 5);
addEdge(4, 3, 2);
// addEdge(4, 5, -2);
// Find the shortest path from a
// vertex (here 0).
shortestPath(0);
}
}
```

### Python Implementation

```
# Python program to find single source shortest paths
# in a Directed Acyclic Graph (DAG).
from collections import defaultdict
# V represents the number of Vertices, present
# in the given DAG.
V=6
# INF means infinity, which is taken
# as a very large number.
INF=999999999999
# Node class
class Node:
# v is the vertex,
# and wt is the weight.
def __init__(self, _v, _wt):
self.v=_v
self.wt=_wt
# Graph Class
class Graph:
def __init__(self,V):
# Initializing Adajency list.
self.adj=defaultdict(list)
self.V=V
# Function to add edge u->v of weigth wt.
def addEdge(self, u, v, wt):
self.adj[u].append(Node(v,wt))
# Function to find topological Sort which is always possible
# as the given graph is a DAG.
def topologicalSort(self, v, visited, st):
# Marking v as visited.
visited[v]=True
# Iterating for all the adjacent nodes of v.
for node in self.adj[v]:
# If any adjacent node to v is not
# visited, call topologicalSort function on it.
if(visited[node.v]==False):
self.topologicalSort(node.v, visited, st)
# Push v into Stack
st.append(v)
# Function to compute the shortest path
# to all other vertices starting from src.
def shortestPath(self, src):
# Declare a Stack (st) which is used to find
# the topological sort of the given DAG.
st=[]
# Declare a dist array where dist[i] denotes
# shortest distance of src from i.
# Initialize all it's entries with INF and
# dist[src] with 0.
dist=[INF]*self.V
# for(i in range(V)):
# dist[i]=INF
dist[src]=0
# Create boolean visited array to keep track
# of visited elements.
visited = [False]*self.V
# for(int i=0i<Vi++)
# visited[i]=false
# Iterate for all the V vertices.
for i in range(V):
# If 'i' found to unvisited call
# topoplogicalSort from there.
if visited[i] == False:
self.topologicalSort(i,visited,st)
# Iterate till the stack is not empty.
while len(st)>0:
# Pop element from stack and store it in u.
u=st.pop()
# If shortest distance from src to u is
# not infinity i.e. it is reachable.
if dist[u]!=INF:
# Iterate for all the adjacent vertices
# of u.
for node in self.adj[u]:
# If distance of src->v is greater than
# distance of src->u + u->v then update
# the value as shown.
if dist[node.v] > dist[u]+node.wt:
dist[node.v] = dist[u] + node.wt
# Prinit the distances.
for i in range(V):
if dist[i]==INF:
print("INF"),
else:
print(dist[i]),
g=Graph(V)
# Add edges.
g.addEdge(0, 2, 4)
g.addEdge(1, 0, 3)
g.addEdge(2, 3,-3)
g.addEdge(2, 4, 2)
g.addEdge(1, 2, 2)
g.addEdge(1, 3, 5)
g.addEdge(4, 3, 2)
# Find the shortest path from a
# vertex (here 0).
g.shortestPath(0)
```

## Complexity Analysis

**Time Complexity –**For a graph $G=(V,E)$ time taken to find the topological ordering is $O(V+E)$. After that, for every vertex $V_i$ we run a loop to its adjacent vertices. So time taken in this step is also $O(V + E)$.

Hence the overall time complexity is $O(V+E)$.**Space Complexity –**We are using a*visited*array of size $V$ and Stack which will be of size $V$, so the overall space complexity is $O(V)$.

## Conclusion

- In the case of the Directed Acyclic Graphs (DAG), finding the topological ordering of the vertices can help us to find the single source shortest paths in $O(V+E)$ time.
- Unlike the Bellman Ford algorithm which takes $O(V\times E)$ time to calculate the same.
- Application: Shortest path algorithm helps to find the nearest location such as restaurants, hotels in maps.