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

```\$ g++ ShortestPathDAG.cpp
\$ a.out

Following are shortest distances from source 1
INF 0 2 6 5 3
------------------
(program exited with code: 0) 