fork download
copy 
  1. // c++ program to find uhortest weighted 
  2. // cycle in undirected graph 
  3.  
  4. #include <iostream>
  5. #include <list>
  6. #include <utility>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <set>
  10. #include <climits>
  11. using namespace std;
  12. # define INF 0x3f3f3f3f 
  13. struct Edge
  14. {
  15. 	int u;
  16. 	int v;
  17. 	int weight;
  18. };
  19.  
  20. // weighted undirected Graph 
  21. class Graph
  22. {
  23. 	int V;
  24. 	list < pair <int, int > >* adj;
  25.  
  26. 	// used to store all edge information 
  27. 	vector < Edge > edge;
  28. 	vector<int> pi;
  29.  
  30.  
  31. public:
  32. 	Graph(int V)
  33. 	{
  34. 		this->V = V;
  35. 		adj = new list < pair <int, int > >[V];
  36. 		pi.assign(V, INF);
  37. 	}
  38.  
  39. 	void addEdge(int u, int v, int w);
  40. 	void removeEdge(int u, int v, int w);
  41. 	int ShortestPath(int u, int v);
  42. 	void RemoveEdge(int u, int v);
  43. 	void FindMinimumCycle();
  44.  
  45. };
  46.  
  47. //function add edge to graph 
  48. void Graph::addEdge(int u, int v, int w)
  49. {
  50. 	adj[u].push_back(make_pair(v, w));
  51. 	adj[v].push_back(make_pair(u, w));
  52.  
  53. 	// add Edge to edge list 
  54. 	Edge e{ u, v, w };
  55. 	edge.push_back(e);
  56. }
  57.  
  58. // function remove edge from undirected graph 
  59. void Graph::removeEdge(int u, int v, int w)
  60. {
  61. 	adj[u].remove(make_pair(v, w));
  62. 	adj[v].remove(make_pair(u, w));
  63. }
  64.  
  65. // find shortest path from source to sink using 
  66. // Dijkstra’s shortest path algorithm [ Time complexity 
  67. // O(E logV )] 
  68. int Graph::ShortestPath(int u, int v) //uはソース、vはシンク
  69. {
  70. 	pi.assign(V, INF);
  71. 	// Create a set to store vertices that are being 
  72. 	// prerocessed 
  73. 	set< pair<int, int> > setds;
  74.  
  75. 	// Create a vector for distances and initialize all 
  76. 	// distances as infinite (INF) 
  77. 	vector<int> dist(V, INF); //値がINFであるV個の要素からなるベクター
  78.  
  79. 	// Insert source itself in Set and initialize its 
  80. 	// distance as 0. 
  81. 	setds.insert(make_pair(0, u)); //ペアの最初の要素は距離、2番目の要素は点のラベル
  82. 	dist[u] = 0;
  83.  
  84. 	/* Looping till all shortest distance are finalized
  85. 	then setds will become empty */
  86. 	while (!setds.empty())
  87. 	{
  88. 		// The first vertex in Set is the minimum distance 
  89. 		// vertex, extract it from set. 
  90. 		pair<int, int> tmp = *(setds.begin());
  91. 		setds.erase(setds.begin());
  92.  
  93. 		// vertex label is stored in second of pair (it 
  94. 		// has to be done this way to keep the vertices 
  95. 		// sorted distance (distance must be first item 
  96. 		// in pair) 
  97. 		int u = tmp.second;
  98.  
  99. 		// 'i' is used to get all adjacent vertices of 
  100. 		// a vertex 
  101. 		list< pair<int, int> >::iterator i;
  102. 		for (i = adj[u].begin(); i != adj[u].end(); ++i) //uに隣接するすべての点に対して
  103. 		{
  104. 			// Get vertex label and weight of current adjacent 
  105. 			// of u. 
  106. 			int v = (*i).first; //uに隣接する点のラベル
  107. 			int weight = (*i).second; //辺(u, v)の重み
  108.  
  109. 			// If there is shorter path to v through u. 
  110. 			if (dist[v] > dist[u] + weight)
  111. 			{
  112. 				/* If distance of v is not INF then it must be in
  113. 					our set, so removing it and inserting again
  114. 					with updated less distance.
  115. 					Note : We extract only those vertices from Set
  116. 					for which distance is finalized. So for them,
  117. 					we would never reach here. */
  118. 				if (dist[v] != INF) //vの暫定的な距離が∞でないということは、既に、(dist[v], v)はsetdsに入っているので、消去する。（↓でdist[v]を更新して再度setdsに挿入している。）
  119. 					setds.erase(setds.find(make_pair(dist[v], v)));
  120.  
  121. 				// Updating distance of v 
  122. 				dist[v] = dist[u] + weight;
  123. 				setds.insert(make_pair(dist[v], v));
  124. 				pi[v] = u;
  125. 			}
  126. 		}
  127. 	}
  128.  
  129. 	// return shortest path from current source to sink 
  130. 	return dist[v];
  131. }
  132.  
  133. // function return minimum weighted cycle 
  134. //int Graph::FindMinimumCycle()
  135. void Graph::FindMinimumCycle()
  136. {
  137. 	int min_cycle = INT_MAX;
  138. 	int E = edge.size();
  139. 	vector<int> pi2;
  140. 	int u = 0, v = 0;
  141. 	for (int i = 0; i < E; i++)
  142. 	{
  143. 		// current Edge information 
  144. 		Edge e = edge[i];
  145.  
  146. 		// get current edge vertices which we currently 
  147. 		// remove from graph and then find shortest path 
  148. 		// between these two vertices using Dijkstra’s 
  149. 		// shortest path algorithm . 
  150. 		removeEdge(e.u, e.v, e.weight);
  151.  
  152. 		// minimum distance between these two vertices 
  153. 		int distance = ShortestPath(e.u, e.v);
  154.  
  155. 		// to make a cycle we have to add weight of 
  156. 		// currently removed edge if this is the shortest 
  157. 		// cycle then update min_cycle 
  158. 		//min_cycle = min(min_cycle, distance + e.weight);
  159. 		if (distance + e.weight < min_cycle)
  160. 		{
  161. 			min_cycle = distance + e.weight;
  162. 			pi2 = pi;
  163. 			u = e.u;
  164. 			v = e.v;
  165. 		}
  166.  
  167. 		// add current edge back to the graph 
  168. 		addEdge(e.u, e.v, e.weight);
  169. 	}
  170.  
  171.  
  172. 	// return shortest cycle 
  173. 	//return min_cycle;
  174.  
  175. 	std::cout << "A minimum weight cycle is:" << endl;
  176.  
  177. 	int v1;
  178. 	v1 = v;
  179. 	while (pi2[v1] != INF)
  180. 	{
  181. 		std::cout << v1 << " -> ";
  182. 		v1 = pi2[v1];
  183. 	}
  184. 	std::cout << u << " -> " << v << endl;
  185.  
  186. 	std::cout << "The weight of the cycle is " << min_cycle << endl;
  187. }
  188.  
  189. // vriver program to test above function 
  190. int main()
  191. {
  192. 	int V = 9;
  193. 	Graph g(V);
  194.  
  195. 	// making above shown graph 
  196. 	g.addEdge(0, 1, 4);
  197. 	g.addEdge(0, 7, 8);
  198. 	g.addEdge(1, 2, 8);
  199. 	g.addEdge(1, 7, 11);
  200. 	g.addEdge(2, 3, 7);
  201. 	g.addEdge(2, 8, 2);
  202. 	g.addEdge(2, 5, 4);
  203. 	g.addEdge(3, 4, 9);
  204. 	g.addEdge(3, 5, 14);
  205. 	g.addEdge(4, 5, 10);
  206. 	g.addEdge(5, 6, 2);
  207. 	g.addEdge(6, 7, 1);
  208. 	g.addEdge(6, 8, 6);
  209. 	g.addEdge(7, 8, 7);
  210.  
  211. 	g.FindMinimumCycle();
  212. 	return 0;
  213. }
  214.  
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
A minimum weight cycle is:
8 -> 6 -> 5 -> 2 -> 8
The weight of the cycle is 14
https://ideone.com/pShuim
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

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!