Floyd求最小环
令e(u, v)表示u和v之间的连边,令min(u, v)表示删除u和v之间的连边之后u和v之间的最短路, 最小环则是min(u, v) + e(u, v). 时间复杂度是 O(EV^2).
改进算法
在floyd的同时,顺便算出最小环
g[i][j]=i, j之间的边长
dist:=g;
for k:=1 to n do begin for i:=1 to k-1 do for j:=i+1 to k-1 do answer:=min(answer, dist[i][j]+g[i][k]+g[k][j]);
for i:=1 to n do for j:=1 to n do dist[i][j]:=min(dist[i][j], dist[i][k]+dist[k][j]);
end;
最小环改进算法的证明
一个环中的最大结点为k(编号最大), 与他相连的两个点为i, j, 这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中所有结点编号都小于k的最短路径长度. 根据floyd的原理, 在最外层循环做了k-1次之后, dist[i][j]则代表了i到j的路径中所有结点编号都小于k的最短路径综上所述,该算法一定能找到图中最小环。
const int INF = 0x3f3f3f3f;
const int MAXN = 110;
int n, m; // n:节点个数, m:边的个数
int g[MAXN][MAXN]; // 无向图
int dist[MAXN][MAXN]; // 最短路径
int r[MAXN][MAXN]; // r[i][j]: i到j的最短路径的第一步
int out[MAXN], ct; // 记录最小环
int solve(int i, int j, int k)
{ // 记录最小环
ct = 0;
while (j != i)
{
out[ct++] = j;
j = r[i][j];
}
out[ct++] = i;
out[ct++] = k;
return 0;
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
int i, j, k;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
g[i][j] = INF;
r[i][j] = i;
}
}
for (i = 0; i < m; i++)
{
int x, y, l;
scanf("%d%d%d", &x, &y, &l);
--x;
--y;
if (l < g[x][y])
{
g[x][y] = g[y][x] = l;
}
}
memmove(dist, g, sizeof(dist));
int Min = INF; // 最小环
for (k = 0; k < n; k++)
{ // Floyd
for (i = 0; i < k; i++) // 一个环中的最大结点为k(编号最大)
{
if (g[k][i] < INF)
{
for (j = i + 1; j < k; j++)
{
if (dist[i][j] < INF && g[k][j] < INF && Min > dist[i][j] + g[k][i] + g[k][j])
{
Min = dist[i][j] + g[k][i] + g[k][j];
solve(i, j, k); // 记录最小环
}
}
}
}
for (i = 0; i < n; i++)
{
if (dist[i][k] < INF)
{
for (j = 0; j < n; j++)
{
if (dist[k][j] < INF && dist[i][j] > dist[i][k]+dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
r[i][j] = r[k][j];
}
}
}
}
}
if (Min < INF)
{
for (ct--; ct >= 0; ct--)
{
printf("%d", out[ct] + 1);
if (ct)
{
printf(" ");
}
}
}
else
{
printf("No solution.");
}
printf("\n");
}
return 0;
}