Given positive weighted undirected graph, find minimum weight cycle in it.
The idea is to use shortest path algorithm. We one by one remove every edge from graph, then we find shortest path between two corner vertices of it. We add an edge back before we process next edge.
1). create an empty vector 'edge' of size 'E' ( E total number of edge). Every element of this vector is used to store information of all the edge in graph info 2) Traverse every edge edge[i] one - by - one a). First remove 'edge[i]' from graph 'G' b). get current edge vertices which we just removed from graph c). Find the shortest path between them "Using Dijkstra’s shortest path algorithm " d). To make a cycle we add weight of the removed edge to the shortest path. e). update min_weight_cycle if needed 3). return minimum weighted cycle
Below c++ implementation of above idea
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.