# Bellman Ford Algorithm for DAG

The idea behind running bellman ford algorithm on a directed acyclic graph is as below

• In a directed acyclic graph ( D. A. G ) ( i.e containing no cycles ), if there exits a path from vertex A leading to vertex B, then vertex A has to come before vertex B in a topologically sorted order.
• Thus if path P = { A, v1, v2, v3, …, vk, B } is the shortest path between vertex A and vertex B, the edges in the path P are relaxed in order
( A, v1 ), ( v1, v2 ), ( v2, v3 ), … ( vk, B )
Thus,
Edge Relaxation
If ( distance [ adjacent-node ] > distance [ current-source-node ] + weight-of-path-from-current-source-to-adjacent-node ) then

EdgeWeight is a map of edges and their corresponding weights in the graph G.
AdjacencyList stores the list of vertices adjacent to a given vertex in the graph G.

Algorithm : BellmanFord for directed acyclic graph ( Source node S )
1.    Topologically sort the vertices of the graph G
2.    Initialize the distance from the source node S to all other nodes as infinite (999999999) and to itself as 0.
Distance [ all_nodes ] = 999999999, Distance [ S ] = 0.
3.    For each vertex u, taken in the topologically sorted order
4.       For each vertex v adjacent to vertex u in the graph G
weight_u_v = EdgeWeight ( u, v )
5.            If ( Distance [ v ] > Distance [ u ] + Weight_u_v )
6.                 Distance [ v ] = Distance [ u ] + weight_u_v

In the below graph, the topological sorting order of the nodes is : 1 6 3 0 5 2 4
The edges are tried for relaxation in the order : [ 1 - 3 ], [ 1 - 6 ], [ 6 - 0 ], [ 6 - 2 ], [ 3 - 5 ], [ 0 - 2 ], [ 0 - 5 ], [ 5 - 2 ], [ 5 - 4 ], [ 2 - 4 ] Data structure used for storing graph : Adjacency List
Data structure used for topological sorting : Stack
Time complexity of Bellman-Ford algorithm for directed acyclic graph : O ( V + E ) for an adjacency list implementation of a graph. V is the number of vertices and E is the number of edges in a graph.

Bellman Ford implementation for DAG [Directed Acyclic Graph]

``````from collections import deque
from collections import defaultdict

class Graph:

def __init__(self, arg_node_cnt):
# Store the adjacency list as a dictionary
# The default dictionary would create an empty list as a default (value)
# for the nonexistent keys.
self.node_cnt = arg_node_cnt
self.visited = [False] * arg_node_cnt
self.edge_weight = {} # Store the weight of each edge
# Note : The edge weight are stored in dictionary like below
# {'0-2': 2, '0-5': 3, '1-3': 2, '1-6': 4, '2-4': 1, '3-5': 1, '5-2': -2, '5-4': 5, '6-0': -3, '6-2': -1}
self.stack_topological_order = deque() # Stack for storing the topologically sorted order of the vertices.

def AddEdgeWeight (self, src, dst, weight):
self.edge_weight[str(src) + "-" + str(dst)] = weight

def TopologicalSort (self, src) :

self.visited[src] = True

# Check if there is an outgoing edge for a node in the adjacency list
if self.visited[node] == False :
self.TopologicalSort(node)

# Only after all the nodes on the outgoing edges are visited push the
# source node in the stack
self.stack_topological_order.appendleft(src)

def BellmanFord_On_DAG (self, source_node):

# Topologically sort the nodes
for i in range(self.node_cnt):
if self.visited[i] == False :
self.TopologicalSort(i)

# Initialize the distance of all the nodes from the source node to infinity
dist =  * self.node_cnt
# Distance of source node to itself is 0
dist[source_node] = 0

print("Topological Sorting Order: ", end = " ")
while self.stack_topological_order :

u = self.stack_topological_order.popleft()

print(str(u), end = " ")

# For each vertex 'v' adjacent to vertex 'u' relax the edge u-v
if u in self.adjlist: # Check if there exist nodes adjacent to node u
weight = self.edge_weight[str(u) + "-" + str(v)]
if (dist[v] > dist[u] + weight):
dist[v] = dist[u] + weight

print("\nShortest Path from source node : " + str(source_node))
for i in range(self.node_cnt) :
print("Source Node(" + str(source_node) + ") -> Destination Node(" + str(i) + ") : Length => " + str(dist[i]))

def main():
g = Graph (7)
# Store the edges of the directed graph in adjacency list.

source_node = 1
g.BellmanFord_On_DAG(source_node)

if __name__ == "__main__":
main()
``````

Output

``````Topological Sorting Order:  1 6 3 0 5 2 4
Shortest Path from source node : 1
Source Node(1) -> Destination Node(0) : Length => 1
Source Node(1) -> Destination Node(1) : Length => 0
Source Node(1) -> Destination Node(2) : Length => 1
Source Node(1) -> Destination Node(3) : Length => 2
Source Node(1) -> Destination Node(4) : Length => 2
Source Node(1) -> Destination Node(5) : Length => 3
Source Node(1) -> Destination Node(6) : Length => 4

``````
``````#include<iostream>
#include<list>
#include<vector>
#include<stack>
#include<map>

using namespace std;

typedef pair<int,int> PII;

class Graph {

private:
int nodes;
vector<bool> visited;
stack<int> stack_topological_order;
map<PII,int> edge_weight;

public:
Graph() {
}

Graph (int nodes) {
visited.resize(nodes, false);
this->nodes = nodes;
}

~Graph () {
}

void AddEdgeWeight (int src, int dst, int weight) {
edge_weight.insert(pair<PII,int>(make_pair(src, dst), weight));
}

void AddEdge (int src, int dst) {
}

void TopologicalSort (int src) {
visited[src] = true;
for (auto& itr : adjlist[src]) {
if (!visited[itr]) {
TopologicalSort(itr);
}
}

/* Only after all the outgoing edges are visited push the
source node in the stack */
stack_topological_order.push(src);
}

void BellmanFord_On_DAG (int source_node) {

// Topologically sort the nodes
for (int i=0; i<nodes; i++) {
if (!visited[i]) {
TopologicalSort(i);
}
}

vector<int> dist(nodes, 999999999);
dist[source_node] = 0;

cout << "Topological Sorting Order : ";
while (!stack_topological_order.empty()) {

int u = stack_topological_order.top();
stack_topological_order.pop();

cout << u << " ";
// For each vertex 'v' adjacent to vertex 'u' relax the edge u-v
int weight = edge_weight.find(make_pair(u,v))->second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
}
}
}

cout << endl << "Shortest Path from source node : " << source_node << endl;
for (int i=0;i<nodes;i++)
cout << "Source Node(" << source_node << ") -> Destination Node(" << i << ") : " << dist[i] << endl;
}
};

int main()
{
Graph g(7);
// Store the edges of the directed graph in adjacency list.

int source_node = 1;
g.BellmanFord_On_DAG(source_node);

return 0;
}
``````

Output

``````Topological Sorting Order : 1 6 3 0 5 2 4
Shortest Path from source node : 1
Source Node(1) -> Destination Node(0) :  Length => 1
Source Node(1) -> Destination Node(1) :  Length => 0
Source Node(1) -> Destination Node(2) :  Length => 1
Source Node(1) -> Destination Node(3) :  Length => 2
Source Node(1) -> Destination Node(4) :  Length => 2
Source Node(1) -> Destination Node(5) :  Length => 3
Source Node(1) -> Destination Node(6) :  Length => 4
``````
``````import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Stack;
import java.util.HashMap;

class Graph {

int nodes;
boolean[] visited;
Stack<Integer> stack_topological_order;
HashMap<String, Integer> edge_weight;

Graph (int nodes) {

this.nodes = nodes;
for (int i=0; i<nodes; i++)
visited = new boolean[nodes];
edge_weight = new HashMap<String, Integer>();
stack_topological_order = new Stack<>();
}

void AddEdgeWeight (String edge, int weight) {
edge_weight.put(edge, weight);
}

void AddEdge (int src, int dst) {
}

void TopologicalSort (int src) {
visited[src] = true;
for (int node : adjlist.get(src)) {
if (!visited[node]) {
TopologicalSort(node);
}
}

/* Only after all the nodes on the outgoing edges are visited push the
source node in the stack */
stack_topological_order.push(src);
}

void BellmanFord_On_DAG (int source_node) {

// Topologically sort the nodes
for (int i=0; i<nodes; i++) {
if (!visited[i]) {
TopologicalSort(i);
}
}

// Initialize the distance/cost from the source node to all other nodes to some max value.
Long INF = (long) 999999999;
List<Long> dist = new ArrayList<Long>(Collections.nCopies(nodes, INF));

// Distance/cost from the source node to itself is 0.
dist.set(source_node, (long) 0);

System.out.print("Topological Sorting Order: ");

while (!stack_topological_order.empty()) {

int u = stack_topological_order.pop();

System.out.print(u + " ");
// For each vertex 'v' adjacent to vertex 'u' relax the edge u-v
int weight = edge_weight.get(u+"-"+v);
if (dist.get(v) > dist.get(u) + weight) {
dist.set(v, dist.get(u) + weight);
}
}
}

System.out.println("\nShortest Path from source node:" + source_node);
for (int i=0; i<nodes; i++)
System.out.println("Source Node(" + source_node + ") -> Destination Node(" + i + ") : Length => " + dist.get(i));
}

public static void main (String [] args) {

Graph g = new Graph(7);

// Store the edges of the directed graph in adjacency list.

int source_node = 1;
g.BellmanFord_On_DAG(source_node);
}
}
``````

Output

``````Topological Sorting Order: 1 6 3 0 5 2 4
Shortest Path from source node:1
Source Node(1) -> Destination Node(0) :  Length => 1
Source Node(1) -> Destination Node(1) :  Length => 0
Source Node(1) -> Destination Node(2) :  Length => 1
Source Node(1) -> Destination Node(3) :  Length => 2
Source Node(1) -> Destination Node(4) :  Length => 2
Source Node(1) -> Destination Node(5) :  Length => 3
Source Node(1) -> Destination Node(6) :  Length => 4
``````