Running Bellman Ford Algorithm on DAG
Bellman Ford Algorithm for DAG (Directed Acyclic Graph)
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 ( ) 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 [ AllNodes ] = 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
Edge Relaxation
if (distance[adjacent-node] > distance[source-node] + weight-of-path-to-adjacent-node) {
distance[adjacent-node] = distance[source-node] + weight-of-path-to-adjacent-node
}
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.
C++ : Bellman Ford algorithm for directed acyclic graph
#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) : 1
Source Node(1) -> Destination Node(1) : 0
Source Node(1) -> Destination Node(2) : 1
Source Node(1) -> Destination Node(3) : 2
Source Node(1) -> Destination Node(4) : 2
Source Node(1) -> Destination Node(5) : 3
Source Node(1) -> Destination Node(6) : 4