fork download 
  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. 		weightPairs[{u, v}] = weight;
  34.  
  35. 		adj[u].push_back(v); 
  36.  
  37. 		++m; 
  38.  
  39. 		if(!isDirected && u != v)
  40. 			adj[v].push_back(u);
  41. 	} 
  42.  
  43. 	void deleteEdge(int u, int v){ 
  44.  
  45. 		if(u >= n || v >=n || u < 0 || v < 0){
  46. 			cout<<"Either of the vertices doesn't exists in the graph.\n";
  47. 			return;
  48. 		}
  49.  
  50. 		auto itr = find(adj[u].begin(), adj[u].end(), v);
  51.  
  52. 		if(itr == adj[u].end()){ 
  53. 			cout<<"The edge doesn't exists in the graph.\n";
  54. 			return; 
  55. 		} 
  56.  
  57. 		adj[u].erase(itr); --m;
  58.  
  59. 		if(!isDirected && u != v){
  60. 			itr = find(adj[v].begin(), adj[v].end(), u);
  61. 			adj[v].erase(itr);
  62. 		}
  63. 	} 
  64.  
  65. 	void displayGraph(){ 
  66.  
  67. 		if(!m){ 
  68. 			cout<<"The graph is empty!!\n";
  69. 			return;
  70. 		} 
  71.  
  72. 		cout<<"Total # edges in the graph: "<<m<<"\n";
  73.  
  74. 		for(int i = 0; i < n; ++i){ 
  75. 			cout<<"The edges from vertex "<<i<<":";
  76.  
  77. 			for(auto val: adj[i])  
  78. 				cout<<"->"<<val;
  79.  
  80. 			cout<<"\n"; 
  81. 		}
  82. 		cout<<"=======================================================\n";
  83. 	}
  84.  
  85. 	void singleSourceShortestPath(int src){
  86.  
  87. 		/*================= Keys & predecessors initialization =================*/
  88. 		vector<int> shortestPaths(n, INT_MAX), predecessors(n, -1);
  89. 		/*================= Keys & predecessors initialization =================*/
  90.  
  91. 		shortestPaths[src] = 0;
  92.  
  93. 		int u, v;
  94.  
  95. 		for(int i=1; i<n; ++i){
  96.  
  97. 			for(auto &edge: weightPairs){
  98.  
  99. 				u = edge.first.first, v = edge.first.second;
  100.  
  101. 				int distUtoV = edge.second;
  102.  
  103. 				if(shortestPaths[u] != INT_MAX && shortestPaths[u] + distUtoV < shortestPaths[v]){
  104. 					predecessors[v] = u;
  105. 					shortestPaths[v] = shortestPaths[u] + distUtoV;
  106. 				}
  107. 			}
  108.  
  109. 		}
  110.  
  111. 		bool flag = true;
  112.  
  113. 		for(auto &edge: weightPairs){
  114.  
  115. 			u = edge.first.first, v = edge.first.second;
  116.  
  117. 			int distUtoV = edge.second;
  118.  
  119. 			if(shortestPaths[u] != INT_MAX && shortestPaths[u] + distUtoV < shortestPaths[v]){
  120. 				cout<<"Graph contains negative cycles.\n"
  121. 				"No shortest path exits from given source to other nodes.\n";
  122. 				flag = false;
  123. 				break;
  124. 			}
  125. 		}
  126.  
  127. 		if(flag){
  128. 			cout<<"The shortest paths from given source are,\n";
  129.  
  130. 			for(int u = 0; u < n; ++u){
  131. 				if(u != src){
  132. 					cout<<"----------------------------------------\n";
  133. 					if(shortestPaths[u] < INT_MAX){
  134. 						cout<<"Path length: "<<shortestPaths[u]<<" | Path: ";
  135. 						printPath(predecessors, u);
  136. 						cout<<"\n";
  137. 					}
  138. 					else{
  139. 						cout<<"No path exits from given source "<<src<<" to "<<u<<"\n";
  140. 					}
  141. 				}
  142. 			}
  143. 		}
  144. 	}
  145.  
  146. 	void printPath(vector<int> &predecessors, int &par){
  147. 		if(par == -1)
  148. 			return;
  149.  
  150. 		printPath(predecessors, predecessors[par]);
  151.  
  152. 		cout<<(predecessors[par] == -1 ? "":"->")<<par;
  153. 	}
  154. };
  155.  
  156. int main() {
  157. 	// your code goes here
  158. 	int n, u, v, w; 
  159. 	cin>>n;
  160.  
  161. 	Graph g(n, 1);
  162.  
  163. 	cin>>n;
  164.  
  165. 	for(int i=0; i < n; ++i){
  166. 		cin>>u>>v>>w;
  167. 		g.insertEdge(u,v,w);
  168. 	}
  169.  
  170. 	g.displayGraph();
  171.  
  172. 	cin>>u;
  173. 	cout<<"Enter the source vertex for single source shortest path\n"
  174. 	"using Bellman-Ford algorithm: "<<u<<"\n";
  175. 	cout<<"------------------------------------------------------\n";
  176.  
  177. 	g.singleSourceShortestPath(u);
  178.  
  179. 	return 0;
  180. }
  181.  
Success #stdin #stdout 0s 4284KB
comments (?)
stdin 
5 10
0 1 6
1 2 5
1 3 -4
1 4 8
2 1 -2
3 2 7
3 0 2
4 0 7
4 2 -3
4 3 9
2
stdout 
Total # edges in the graph: 10
The edges from vertex 0:->1
The edges from vertex 1:->2->3->4
The edges from vertex 2:->1
The edges from vertex 3:->2->0
The edges from vertex 4:->0->2->3
=======================================================
Enter the source vertex for single source shortest path
using Bellman-Ford algorithm: 2
------------------------------------------------------
The shortest paths from given source are,
----------------------------------------
Path length: -4 | Path: 2->1->3->0
----------------------------------------
Path length: -2 | Path: 2->1
----------------------------------------
Path length: -6 | Path: 2->1->3
----------------------------------------
Path length: 6 | Path: 2->1->4
https://ideone.com/DPperb
Single source shortest path using Bellman-Ford for negatively weighted graph || Time complexity: O(VE)
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!