C++ Program to 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.

Here is source code of the C++ Program to Implement Shortest Path Algorithm for DAG Using Topological Sorting. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // A C++ program to find single source shortest paths for Directed Acyclic Graphs
  2. #include<iostream>
  3. #include <list>
  4. #include <stack>
  5. #include <limits.h>
  6. #define INF INT_MAX
  7. using namespace std;
  8.  
  9. class AdjListNode
  10. {
  11.         int v;
  12.         int weight;
  13.     public:
  14.         AdjListNode(int _v, int _w)
  15.         {
  16.             v = _v;
  17.             weight = _w;
  18.         }
  19.         int getV()
  20.         {
  21.             return v;
  22.         }
  23.         int getWeight()
  24.         {
  25.             return weight;
  26.         }
  27. };
  28.  
  29. // Class to represent a graph using adjacency list representation
  30. class Graph
  31. {
  32.         int V; // No. of vertices'
  33.  
  34.         // Pointer to an array containing adjacency lists
  35.         list<AdjListNode> *adj;
  36.  
  37.         // A function used by shortestPath
  38.         void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
  39.     public:
  40.         Graph(int V); // Constructor
  41.  
  42.         // function to add an edge to graph
  43.         void addEdge(int u, int v, int weight);
  44.  
  45.         // Finds shortest paths from given source vertex
  46.         void shortestPath(int s);
  47. };
  48.  
  49. Graph::Graph(int V)
  50. {
  51.     this->V = V;
  52.     adj = new list<AdjListNode> [V];
  53. }
  54.  
  55. void Graph::addEdge(int u, int v, int weight)
  56. {
  57.     AdjListNode node(v, weight);
  58.     adj[u].push_back(node); // Add v to u's list
  59. }
  60.  
  61. void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
  62. {
  63.     // Mark the current node as visited
  64.     visited[v] = true;
  65.  
  66.     // Recur for all the vertices adjacent to this vertex
  67.     list<AdjListNode>::iterator i;
  68.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  69.     {
  70.         AdjListNode node = *i;
  71.         if (!visited[node.getV()])
  72.             topologicalSortUtil(node.getV(), visited, Stack);
  73.     }
  74.  
  75.     // Push current vertex to stack which stores topological sort
  76.     Stack.push(v);
  77. }
  78.  
  79. void Graph::shortestPath(int s)
  80. {
  81.     stack<int> Stack;
  82.     int dist[V];
  83.  
  84.     // Mark all the vertices as not visited
  85.     bool *visited = new bool[V];
  86.     for (int i = 0; i < V; i++)
  87.         visited[i] = false;
  88.  
  89.     // Call the recursive helper function to store Topological Sort
  90.     // starting from all vertices one by one
  91.     for (int i = 0; i < V; i++)
  92.         if (visited[i] == false)
  93.             topologicalSortUtil(i, visited, Stack);
  94.  
  95.     // Initialize distances to all vertices as infinite and distance
  96.     // to source as 0
  97.     for (int i = 0; i < V; i++)
  98.         dist[i] = INF;
  99.     dist[s] = 0;
  100.  
  101.     // Process vertices in topological order
  102.     while (Stack.empty() == false)
  103.     {
  104.         // Get the next vertex from topological order
  105.         int u = Stack.top();
  106.         Stack.pop();
  107.  
  108.         // Update distances of all adjacent vertices
  109.         list<AdjListNode>::iterator i;
  110.         if (dist[u] != INF)
  111.         {
  112.             for (i = adj[u].begin(); i != adj[u].end(); ++i)
  113.                 if (dist[i->getV()] > dist[u] + i->getWeight())
  114.                     dist[i->getV()] = dist[u] + i->getWeight();
  115.         }
  116.     }
  117.  
  118.     // Print the calculated shortest distances
  119.     for (int i = 0; i < V; i++)
  120.         (dist[i] == INF) ? cout << "INF " : cout << dist[i] << " ";
  121. }
  122.  
  123. // Driver program to test above functions
  124. int main()
  125. {
  126.     // Create a graph given in the above diagram.  Here vertex numbers are
  127.     // 0, 1, 2, 3, 4, 5 with following mappings:
  128.     // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
  129.     Graph g(6);
  130.     g.addEdge(0, 1, 5);
  131.     g.addEdge(0, 2, 3);
  132.     g.addEdge(1, 3, 6);
  133.     g.addEdge(1, 2, 2);
  134.     g.addEdge(2, 4, 4);
  135.     g.addEdge(2, 5, 2);
  136.     g.addEdge(2, 3, 7);
  137.     g.addEdge(3, 4, -1);
  138.     g.addEdge(4, 5, -2);
  139.  
  140.     int s = 1;
  141.     cout << "Following are shortest distances from source " << s << " \n";
  142.     g.shortestPath(s);
  143.  
  144.     return 0;
  145. }

Output:

advertisement
$ g++ ShortestPathDAG.cpp
$ a.out
 
Following are shortest distances from source 1 
INF 0 2 6 5 3 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement

Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn