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 distance [ adjacent-node ] = distance [ current-source-node ] + weight-of-path-from-current-source-to-adjacent-node
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, node_cnt : int):
# Store the adjacency list as a dictionary
# The default dictionary would create an empty list as a default (value)
# for the nonexistent keys.
self.adjlist = defaultdict(list)
self.node_cnt = node_cnt
self.visited = [False] * 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 : int, dst : int, weight : int):
self.edge_weight[str(src) + "-" + str(dst)] = weight
def AddEdge (self, src : int, dst : int):
self.adjlist[src].append(dst)
def TopologicalSort (self, src : int):
self.visited[src] = True
# Check if there is an outgoing edge for a node in the adjacency list
if src in self.adjlist :
for node in self.adjlist[src] :
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 : int):
# 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 = [999999999999] * 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
for v in self.adjlist[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.
g.AddEdge(0, 2)
g.AddEdgeWeight(0, 2, 2)
g.AddEdge(0, 5)
g.AddEdgeWeight(0, 5, 3)
g.AddEdge(1, 3)
g.AddEdgeWeight(1, 3, 2)
g.AddEdge(1, 6)
g.AddEdgeWeight(1, 6, 4)
g.AddEdge(2, 4)
g.AddEdgeWeight(2, 4, 1)
g.AddEdge(3, 5)
g.AddEdgeWeight(3, 5, 1)
g.AddEdge(5, 2)
g.AddEdgeWeight(5, 2, -2)
g.AddEdge(5, 4)
g.AddEdgeWeight(5, 4, 5)
g.AddEdge(6, 0)
g.AddEdgeWeight(6, 0, -3)
g.AddEdge(6, 2)
g.AddEdgeWeight(6, 2, -1)
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;
list<int> *adjlist;
vector<bool> visited;
stack<int> stack_topological_order;
map<PII,int> edge_weight;
public:
Graph() {
}
Graph (int nodes) {
adjlist = new list<int> [nodes];
visited.resize(nodes, false);
this->nodes = nodes;
}
~Graph () {
delete [] adjlist;
}
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) {
adjlist[src].push_back(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
for (auto& v: adjlist[u]) {
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.
g.AddEdge(0,2);
g.AddEdgeWeight(0,2,2);
g.AddEdge(0,5);
g.AddEdgeWeight(0,5,3);
g.AddEdge(1,3);
g.AddEdgeWeight(1,3,2);
g.AddEdge(1,6);
g.AddEdgeWeight(1,6,4);
g.AddEdge(2,4);
g.AddEdgeWeight(2,4,1);
g.AddEdge(3,5);
g.AddEdgeWeight(3,5,1);
g.AddEdge(5,2);
g.AddEdgeWeight(5,2,-2);
g.AddEdge(5,4);
g.AddEdgeWeight(5,4,5);
g.AddEdge(6,0);
g.AddEdgeWeight(6,0,-3);
g.AddEdge(6,2);
g.AddEdgeWeight(6,2,-1);
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;
List<List<Integer>> adjlist;
boolean[] visited;
Stack<Integer> stack_topological_order;
HashMap<String, Integer> edge_weight;
Graph (int nodes) {
this.nodes = nodes;
adjlist = new ArrayList<>(nodes);
for (int i=0; i<nodes; i++)
adjlist.add(new ArrayList<>());
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) {
adjlist.get(src).add(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
for (int v: adjlist.get(u)) {
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.
g.AddEdge(0,2);
g.AddEdgeWeight("0-2", 2);
g.AddEdge(0,5);
g.AddEdgeWeight("0-5", 3);
g.AddEdge(1,3);
g.AddEdgeWeight("1-3", 2);
g.AddEdge(1,6);
g.AddEdgeWeight("1-6", 4);
g.AddEdge(2,4);
g.AddEdgeWeight("2-4", 1);
g.AddEdge(3,5);
g.AddEdgeWeight("3-5", 1);
g.AddEdge(5,2);
g.AddEdgeWeight("5-2", -2);
g.AddEdge(5,4);
g.AddEdgeWeight("5-4", 5);
g.AddEdge(6,0);
g.AddEdgeWeight("6-0", -3);
g.AddEdge(6,2);
g.AddEdgeWeight("6-2", -1);
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