C++ Program to Find Shortest Path in a 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
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.