fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Graph{
  5. 	public:
  6. 	int n, m;
  7. 	bool isDirected;
  8. 	vector<vector<int>> adj;
  9. 	map<pair<int, int>, int> weightPairs;
  10.  
  11. 	Graph(int nodes): adj(nodes){
  12. 		n = nodes;
  13. 		m = 0;
  14. 	}
  15.  
  16. 	void addEdge(int u, int v, int weight){
  17. 		if(u >= n || v >=n || u < 0 || v < 0){ 
  18. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  19. 			return;
  20. 		}
  21.  
  22. 		weightPairs[{u, v}] = weight;
  23.  
  24. 		adj[u].push_back(v);
  25.  
  26. 		++m;
  27. 	}
  28.  
  29. 	void dfs(int u, vector<bool> &visited, stack<int> &st, bool &useStack){
  30. 		visited[u] = true;
  31.  
  32. 		if(!useStack)
  33. 			cout<<u<<" ";
  34.  
  35. 		for(auto adjNode: adj[u]){
  36. 			if(!visited[adjNode]){
  37. 				dfs(adjNode, visited, st, useStack);
  38.  
  39. 				if(useStack){
  40. 					st.push(adjNode);
  41. 				}
  42. 			}
  43. 		}
  44. 	}
  45.  
  46. 	void singleSourceShortestPath(int src){
  47. 		vector<bool> visited(n, false);
  48. 		stack<int> st; // Stack for storing the topological sort of nodes. 
  49.  
  50. 		bool useStack = true;
  51.  
  52. 		if(!useStack)
  53. 			cout<<"DFS: ";
  54.  
  55. 		for(int i=0; i<n; ++i){
  56. 			if(!visited[i]){
  57. 				dfs(i, visited, st, useStack);
  58.  
  59. 				if(useStack)
  60. 					st.push(i);
  61. 			}
  62. 		}
  63.  
  64. 		visited = vector<bool>(n, false);
  65. 		vector<int> shortestPaths(n, INT_MAX), predecessors(n, -1);
  66.  
  67. 		shortestPaths[src] = 0;
  68.  
  69. 		while(!st.empty()){
  70. 			int u = st.top();
  71.  
  72. 			visited[u] = true;
  73.  
  74. 			for(auto v: adj[u]){
  75.  
  76. 				int distUtoV = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
  77.  
  78. 				if(!visited[v] && shortestPaths[u] != INT_MAX &&
  79. 					distUtoV + shortestPaths[u] < shortestPaths[v]){
  80.  
  81. 					predecessors[v] = u;
  82. 					shortestPaths[v] = distUtoV + shortestPaths[u];
  83. 				}
  84. 			}
  85.  
  86. 			st.pop();
  87. 		}
  88.  
  89. 		cout<<"The shortest paths from given source "<<src<<" to\nall other nodes are,\n";
  90.  
  91. 			for(int u = 0; u < n; ++u){
  92. 				if(u != src){
  93. 					cout<<"----------------------------------------\n";
  94. 					if(shortestPaths[u] < INT_MAX){
  95. 						cout<<"Path length: "<<shortestPaths[u]<<" | Path: ";
  96. 						printPath(predecessors, u);
  97. 						cout<<"\n";
  98. 					}
  99. 					else{
  100. 						cout<<"No path exits from given source "<<src<<" to "<<u<<"\n";
  101. 					}
  102. 				}
  103. 			}
  104.  
  105. 	}
  106.  
  107. 	void printGraph(){ 
  108.  
  109. 		if(!m){ 
  110. 			cout<<"The graph is empty!!\n";
  111. 			return;
  112. 		} 
  113.  
  114. 		cout<<"Total # edges in the graph: "<<m<<"\n";
  115.  
  116. 		for(int i = 0; i < n; ++i){ 
  117. 			cout<<"The edges from vertex "<<i<<":";
  118.  
  119. 			for(auto val: adj[i])  
  120. 				cout<<"->"<<val;
  121.  
  122. 			cout<<"\n"; 
  123. 		}
  124. 		cout<<"======================================================\n";
  125. 	}
  126.  
  127. 	void printPath(vector<int> &predecessors, int par){
  128. 		if(par == -1)
  129. 			return;
  130.  
  131. 		printPath(predecessors, predecessors[par]);
  132.  
  133. 		cout<<(predecessors[par] == -1 ? "":"->")<<par;
  134. 	}
  135. };
  136.  
  137. int main()
  138. {
  139. 	int n, u, v, w; 
  140. 	cin>>n;
  141.  
  142. 	Graph g(n);
  143.  
  144. 	cin>>n;
  145.  
  146. 	for(int i=0; i < n; ++i){
  147. 		cin>>u>>v>>w;
  148. 		g.addEdge(u,v,w);
  149. 	}
  150.  
  151. 	g.printGraph();
  152.  
  153. 	cin>>n;
  154. 	g.singleSourceShortestPath(n);
  155.  
  156. 	return 0;
  157. }
Success #stdin #stdout 0s 4184KB
comments (?)
stdin 
6 10
0 1 5
0 2 3
1 2 2
1 3 6
2 3 7
2 4 4
2 5 2
3 4 -1
3 5 1
4 5 -2
1
stdout 
Total # edges in the graph: 10
The edges from vertex 0:->1->2
The edges from vertex 1:->2->3
The edges from vertex 2:->3->4->5
The edges from vertex 3:->4->5
The edges from vertex 4:->5
The edges from vertex 5:
======================================================
The shortest paths from given source 1 to
all other nodes are,
----------------------------------------
No path exits from given source 1 to 0
----------------------------------------
Path length: 2 | Path: 1->2
----------------------------------------
Path length: 6 | Path: 1->3
----------------------------------------
Path length: 5 | Path: 1->3->4
----------------------------------------
Path length: 3 | Path: 1->3->4->5
https://ideone.com/HhYGbc
Single source shortest path for the Directed Acyclic Graph(DAG with -ve weights) using topological sort || Time complexity: O(n+m)
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!