# 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
} 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++ : Implementation of Bellman Ford algorithm for directed acyclic graph in C++11

``````#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) : 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
``````