fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Graph{ 
  5. public: 
  6. 	int n;
  7. 	int m; 
  8. 	int maxEdges;
  9. 	bool isDirected;
  10.  
  11. 	vector<vector<int>> adj;
  12. 	map<pair<int, int>, int> weightPairs;
  13.  
  14. 	Graph(int nodes, bool isDiGraph) : adj(nodes){ 
  15. 		n = nodes;
  16. 		m = 0;
  17. 		isDirected = isDiGraph; 
  18. 		maxEdges = isDirected ? n*(n-1) : n*(n-1)/2;
  19. 	}
  20.  
  21. 	void insertEdge(int u, int v, int weight){ 
  22.  
  23. 		if(u >= n || v >= n || u < 0 || v < 0){ 
  24. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  25. 			return;
  26. 		}
  27.  
  28. 		if(m == maxEdges){ 
  29. 			cout<<"Maximum allowed edges are already in the graph. Can't insert more.\n";
  30. 			return; 
  31. 		}
  32.  
  33. 		if(isDirected || u != v) 
  34. 			weightPairs[{u, v}] = weight;
  35.  
  36. 		adj[u].push_back(v); ++m;
  37.  
  38. 		if(!isDirected && u != v)
  39. 			adj[v].push_back(u);
  40. 	} 
  41.  
  42. 	void deleteEdge(int u, int v){ 
  43.  
  44. 		if(u >= n || v >=n || u < 0 || v < 0){
  45. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  46. 			return;
  47. 		}
  48.  
  49. 		auto itr = find(adj[u].begin(), adj[u].end(), v);
  50.  
  51. 		if(itr == adj[u].end()){ 
  52. 			cout<<"The edge doesn't exists in the graph.\n";
  53. 			return; 
  54. 		} 
  55.  
  56. 		adj[u].erase(itr); --m;
  57.  
  58. 		if(!isDirected && u != v){
  59. 			itr = find(adj[v].begin(), adj[v].end(), u);
  60. 			adj[v].erase(itr);
  61. 		}
  62. 	} 
  63.  
  64. 	void displayGraph(){ 
  65.  
  66. 		if(!m){ 
  67. 			cout<<"The graph is empty!!\n";
  68. 			return;
  69. 		} 
  70.  
  71. 		cout<<"Total # edges in the graph: "<<m<<"\n";
  72.  
  73. 		for(int i = 0; i < n; ++i){ 
  74. 			cout<<"The edges from vertex "<<i<<":";
  75.  
  76. 			for(auto val: adj[i])  
  77. 				cout<<"->"<<val;
  78.  
  79. 			cout<<"\n"; 
  80. 		}
  81. 		cout<<"======================================================\n";
  82. 	}
  83.  
  84. 	void swap(vector<int> &arr, int i, int j){
  85. 		if(arr[i] != arr[j]){
  86. 			int temp = arr[i];
  87. 			arr[i] = arr[j];
  88. 			arr[j] = temp;
  89. 		}
  90. 	}
  91.  
  92. 	void heapify(vector<int> &nodes, vector<int> &positions,
  93. 				 vector<int> &shortestPaths, int i, int &n){
  94. 		int smallest = i;
  95. 		int left = 2 * smallest + 1, right = left + 1;
  96.  
  97. 		if(left < n && shortestPaths[nodes[left]] < shortestPaths[nodes[smallest]])
  98. 			smallest = left;
  99.  
  100. 		if(right < n && shortestPaths[nodes[right]] < shortestPaths[nodes[smallest]])
  101. 			smallest = right;
  102.  
  103. 		if(smallest ^ i){
  104. 			swap(nodes, smallest, i);
  105.  
  106. 			swap(positions, nodes[smallest], nodes[i]);
  107.  
  108. 			heapify(nodes, positions, shortestPaths, smallest, n);
  109. 		}
  110. 	}
  111.  
  112. 	void singleSourceShortestPath(int src){
  113.  
  114. 		/*================= Keys & predecessors initialization =================*/
  115. 		vector<int> shortestPaths(n, INT_MAX), predecessors(n, -1), nodes(n), positions(n);
  116.  
  117. 		vector<bool> visited(n, false);
  118. 		/*================= Keys & predecessors initialization =================*/
  119.  
  120. 		shortestPaths[src] = 0;
  121.  
  122. 		for(int i = 0; i < n; ++i){
  123. 			nodes[i] = i;
  124. 			positions[i] = i;
  125. 		}
  126.  
  127. 		for(int i=n/2-1; i > -1; --i){ // [O(V)]
  128. 			heapify(nodes, positions, shortestPaths, i, n);
  129. 		}
  130.  
  131. 		/*======================= Start extracting min from heap ========================*/
  132.  
  133. 		for(int i = n-1; i > 0; --i){ // [O(V)]
  134. 	        int u = nodes[0];
  135. 	        visited[u] = true;
  136.  
  137. 	        swap(nodes, 0, i);
  138. 	        swap(positions, nodes[0], nodes[i]);
  139.  
  140. 	        heapify(nodes, positions, shortestPaths, 0, i); // [O(log(V))]
  141.  
  142. 			for(auto v: adj[u]){ // [O(E)]
  143.  
  144. 				int distUtoV = weightPairs[{u, v}] ? weightPairs[{u, v}] : weightPairs[{v, u}];
  145.  
  146. 				if(!visited[v] && shortestPaths[u] != INT_MAX && 
  147. 					distUtoV + shortestPaths[u] < shortestPaths[v]){
  148.  
  149. 					predecessors[v] = u;
  150. 					shortestPaths[v] = distUtoV + shortestPaths[u];
  151.  
  152. 					/*=============== Re-Position [O(log(V))] ================*/
  153. 					for(int vPos = positions[v]; 
  154. 						vPos > 0 && shortestPaths[ nodes[vPos] ] < shortestPaths[ nodes[(vPos - 1)/2] ]; 
  155. 						vPos = (vPos - 1)/2)
  156. 					{
  157. 						swap(nodes, vPos, (vPos - 1)/2);
  158. 						swap(positions, nodes[vPos], nodes[(vPos - 1)/2]);
  159. 					}
  160. 					/*=============== Re-Position [O(log(V))] ================*/
  161. 				}
  162. 			}
  163. 	    }
  164.  
  165. 		/*======================= End of extracting min from heap ========================*/
  166.  
  167. 		cout<<"The shortest paths from given source are,\n";
  168.  
  169. 		for(int u = 0; u < n; ++u){
  170. 			if(u != src){
  171. 				cout<<"----------------------------------------\n";
  172. 				if(shortestPaths[u] < INT_MAX){
  173. 					cout<<"Path length: "<<shortestPaths[u]<<" | Path: ";
  174. 					printPath(predecessors, u);
  175. 					cout<<"\n";
  176. 				}
  177. 				else{
  178. 					cout<<"No path exits from given source "<<src<<" to "<<u<<"\n";
  179. 				}
  180. 			}
  181. 		}
  182.  
  183. 	}
  184.  
  185. 	void printPath(vector<int> &predecessors, int par){
  186. 		if(par == -1)
  187. 			return;
  188.  
  189. 		printPath(predecessors, predecessors[par]);
  190.  
  191. 		cout<<(predecessors[par] == -1 ? "":"->")<<par;
  192. 	}
  193. };
  194.  
  195. int main() {
  196. 	// your code goes here
  197. 	int n, u, v, w; 
  198. 	cin>>n;
  199.  
  200. 	Graph g(n, 1);
  201.  
  202. 	cin>>n;
  203.  
  204. 	for(int i=0; i < n; ++i){
  205. 		cin>>u>>v>>w;
  206. 		g.insertEdge(u,v,w);
  207. 	}
  208.  
  209. 	g.displayGraph();
  210.  
  211. 	cin>>u;
  212. 	cout<<"Enter the source vertex for single source shortest path\n"
  213. 	"using Dijkstra's algorithm: "<<u<<"\n";
  214. 	cout<<"------------------------------------------------------\n";
  215.  
  216. 	g.singleSourceShortestPath(u);
  217.  
  218. 	return 0;
  219. }
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
5
9
0 1 10
0 4 5
1 2 1
1 4 2
2 3 4
3 2 6
4 1 3
4 2 9
4 3 2
0
stdout
copy 
Total # edges in the graph: 9
The edges from vertex 0:->1->4
The edges from vertex 1:->2->4
The edges from vertex 2:->3
The edges from vertex 3:->2
The edges from vertex 4:->1->2->3
======================================================
Enter the source vertex for single source shortest path
using Dijkstra's algorithm: 0
------------------------------------------------------
The shortest paths from given source are,
----------------------------------------
Path length: 8 | Path: 0->4->1
----------------------------------------
Path length: 9 | Path: 0->4->1->2
----------------------------------------
Path length: 7 | Path: 0->4->3
----------------------------------------
Path length: 5 | Path: 0->4
https://ideone.com/wYe5sa
Single source shortest path Directed Acyclic Graph(DAG with ve weights) using Dijkstra's algorithm || Time complexity: O(V log V + E log V)
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!