Find the minimum weight cycle in an undirected graph

Find the minimum weighted cycle in an undirected graph can be found from[1]. An example from [1] is shown here to well explain this problem.

An example of a weighted undirected graph from[1]
Minimum weighed cycle : 7 + 1 + 6 = 14 or
2 + 6 + 2 + 4 = 14 [1]

Q&A from [2]

Q

A

[3] mentions that both Dijkstra and Floyd Warshall algorithm can be used to find the minum weighted cycle in undirected graph.

[6] mentions 3 algorithms used to solve this problem. Except the Digkstra and Floyd Warshall algorithms, a brute force algorithm is also mentioned here. The complexity of each algorithm is analyzed here.

  • brute force O(EV²)
  • by using Dijkstra O(E*(V+E)log V) recall that the Dijkstra algorithm has the complexity of O((V+E)log V)
  • by using Floyd Warshall O(V³)

[5] gives two ample codes used to solve the problem [4].

[7] gave a nice solution for problem [8]

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 1044266558
typedef struct Point
{
int x, y;
Point operator - ( const Point &b ) const
{
Point c;
c.x = x-b.x; c.y = y-b.y;
return c;
}
double operator * ( const Point &b ) const
{
return x*b.y-y*b.x;
}
}Point;
Point h[505], s[505];
int n, m, ans, road[505][505];
bool Jud(Point x, Point y, Point z)
{
if((x.x<z.x && y.x<z.x) || (x.y<z.y && y.y<z.y) || (x.x>z.x && y.x>z.x) || (x.y>z.y && y.y>z.y))
return 1;
return 0;
}
int main(void)
{
int i, j, k, flag;
while(scanf("%d", &n)!=EOF)
{
memset(road, 62, sizeof(road));
for(i=1;i<=n;i++)
scanf("%d%d", &h[i].x, &h[i].y);
scanf("%d", &m);
for(i=1;i<=m;i++)
scanf("%d%d", &s[i].x, &s[i].y);
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
{
flag = 1;
for(k=1;k<=n;k++)
{
if((s[i]-s[j])*(s[i]-h[k])<0 || (s[i]-s[j])*(s[i]-h[k])==0 && Jud(s[i], s[j], h[k]))
{
flag = 0;
break;
}
}
if(flag)
road[i][j] = 1;
}
}
ans = inf;
for(k=1;k<=m;k++)
{
for(i=1;i<=m;i++)
{
if(road[i][k]==inf)
continue;
for(j=1;j<=m;j++)
road[i][j] = min(road[i][j], road[i][k]+road[k][j]);
}
}
for(i=1;i<=m;i++)
ans = min(ans, road[i][i]);
if(ans>m)
printf("ToT\n");
else
printf("%d\n", m-ans);
}
return 0;
}

Reference

[1]https://www.geeksforgeeks.org/find-minimum-weight-cycle-undirected-graph/

[2]https://stackoverflow.com/questions/22738785/minimum-weight-cycles-with-floyd-warshall-algorithm

[3]https://www.cnblogs.com/Yz81128/archive/2012/08/15/2640940.html

[4]http://poj.org/problem?id=1734

[5]https://blog.csdn.net/yo_bc/article/details/75042688

[6]https://oi-wiki.org/graph/min-circle/

[7]https://blog.csdn.net/Jaihk662/article/details/76771320?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-3.nonecase

[8]http://acm.hdu.edu.cn/showproblem.php?pid=608

Data Scientist/MLE/SWE @takemobi