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
}
Bellman Ford Directed Acyclic Graph 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;
        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

Copyright © 2019, Algotree.org.
All rights reserved.