C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Implement Shortest Path Algorithm for DAG Using Topological Sorting



Implement Shortest Path Algorithm for DAG Using Topological Sorting

This is a C++ Program to find shortest path for DAG using topological sorting. For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman-Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra's algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.

    // A C++ program to find single source shortest paths for Directed Acyclic Graphs

    #include<iostream>

    #include <list>

    #include <stack>

    #include <limits.h>

    #define INF INT_MAX

    using namespace std;

    class AdjListNode

    {

            int v;

            int weight;

        public:

            AdjListNode(int _v, int _w)

            {

                v = _v;

                weight = _w;

            }

            int getV()

            {

                return v;

            }

            int getWeight()

            {

                return weight;

            }

    };

    // Class to represent a graph using adjacency list representation

    class Graph

    {

            int V; // No. of vertices'

            // Pointer to an array containing adjacency lists

            list<AdjListNode> *adj;

            // A function used by shortestPath

            void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

        public:

            Graph(int V); // Constructor

            // function to add an edge to graph

            void addEdge(int u, int v, int weight);

            // Finds shortest paths from given source vertex

            void shortestPath(int s);

    };

    Graph::Graph(int V)

    {

        this->V = V;

        adj = new list<AdjListNode> [V];

    }

    void Graph::addEdge(int u, int v, int weight)

    {

        AdjListNode node(v, weight);

        adj[u].push_back(node); // Add v to u's list

    }

    void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)

    {

        // Mark the current node as visited

        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex

        list<AdjListNode>::iterator i;

        for (i = adj[v].begin(); i != adj[v].end(); ++i)

        {

            AdjListNode node = *i;

            if (!visited[node.getV()])

                topologicalSortUtil(node.getV(), visited, Stack);

        }

        // Push current vertex to stack which stores topological sort

        Stack.push(v);

    }

    void Graph::shortestPath(int s)

    {

        stack<int> Stack;

        int dist[V];

        // Mark all the vertices as not visited

        bool *visited = new bool[V];

        for (int i = 0; i < V; i++)

            visited[i] = false;

        // Call the recursive helper function to store Topological Sort starting from all vertices one by one

        for (int i = 0; i < V; i++)

            if (visited[i] == false)

                topologicalSortUtil(i, visited, Stack);

        // Initialize distances to all vertices as infinite and distance to source as 0

        for (int i = 0; i < V; i++)

            dist[i] = INF;

        dist[s] = 0;

        // Process vertices in topological order

        while (Stack.empty() == false)

        {

            // Get the next vertex from topological order

            int u = Stack.top();

            Stack.pop();

            // Update distances of all adjacent vertices

            list<AdjListNode>::iterator i;

            if (dist[u] != INF)

            {

                for (i = adj[u].begin(); i != adj[u].end(); ++i)

                    if (dist[i->getV()] > dist[u] + i->getWeight())

                        dist[i->getV()] = dist[u] + i->getWeight();

            }

        }

        // Print the calculated shortest distances

        for (int i = 0; i < V; i++)

            (dist[i] == INF) ? cout << "INF " : cout << dist[i] << " ";

    }

    // Driver program to test above functions

    int main()

    {

        // Create a graph given in the above diagram.  Here vertex numbers are

        // 0, 1, 2, 3, 4, 5 with following mappings:

        // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z

        Graph g(6);

        g.addEdge(0, 1, 5);

        g.addEdge(0, 2, 3);

        g.addEdge(1, 3, 6);

        g.addEdge(1, 2, 2);

        g.addEdge(2, 4, 4);

        g.addEdge(2, 5, 2);

        g.addEdge(2, 3, 7);

        g.addEdge(3, 4, -1);

        g.addEdge(4, 5, -2);

        int s = 1;

        cout << "Following are shortest distances from source " << s << " \n";

        g.shortestPath(s);

        return 0;

    }