Floyd 最小环算法
思路一
首先，理解 Floyd 算法是按照点的编号增加的顺序更新最短路径的。
因为 Floyd 算法基于动态规划思想，动态规划过程必定存在一个顺序，这里的顺序就是节点编号增加的顺序。那么如果存在这个最小环，会在这个环中的编号最大的那个点 u 更新之前发现这个环。
也就是说，当 u 点被拿来更新从 i 到 j 的最短路径时，我们就能够发现这个闭合环路，发现的方法也不难理解，**if（dis[i][j]+map[j][u]+map[u][i]<INF）**那么就说明以 i 到 j 的一条路径加上 j 到 u 这条边，加上 u 到 i 这条边，就能够组成一个环路。那么我们就在 floyd 实现的代码上稍加改变就可以求得这个最小环。
思路二
我们可以逆向考虑这个问题，假设现在我们已经进行完 floyd 的过程了，dis[i][j]已经是从 i 到 j 的最短路径值了，那么如果我们设定一个数组:pre[i][j]来记录其路径的话，有这样一个方法：
首先我们能够理解，无论对 dis[i][j]这条路径上一共用多少个点更新过这个值，最后一步更新一定是这样的：dis[i][j]=dis[i][k]+dis[k][j]，我们不妨拿出一个栗子来说：
对于 dis[1][5]，假如其最后一次更新是这样的：
dis[1][5]=dis[1][4]+dis[4][5]，
其 dis[1][4]的最后一步更新为：
dis[1][4]=dis[1][2]+dis[2][4]；
我们不难写出其路径：1 2 4 5。
我们这里注意，起点终点就是 dis[i][j]中的 i，j，那么 2 和 4 要如何记录呢？我们可以对其 dis[i][j]最后一次更新的点进行记录，也就是说：pre[1][5]=4；pre[1][4]=2；这个时候，我们发现 5 4 2 之间有相关联：2=pre[1][pre[1][5]]；那么我们不难想出，对于记录路径，我们可以回溯找各个节点。
我们将 pre[i][j]初始化为 i，当其被更新的时候，我们都记录下来那个节点，回溯即可。
代码示例
#include <cstdio>
#include <cstring>
int const MAX = 105;
int const INF = 0xfffffff;
int distMAX, mapMAX, preMAX;
int n, m, ans[MAX], min_loop, cnt;
void init()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
disti = INF;
mapi = INF;
prei = i; //开始时j的上一节点为i
}
}
}
void Floyd()
{
min_loop = INF; //最小环的大小
for (int k = 1; k <= n; k++)
{
//求最小环，最短路不变
for (int i = 1; i < k; i++)
{ //通过k对每一个节点进行优化
for (int j = i + 1; j < k; j++)
{
if (disti + mapi + mapk < min_loop)
{ //出现了更小的环
min_loop = disti + mapi + mapk;
int tmp = j;
cnt = 0;
while (tmp != i)
{
ans[cnt++] = tmp;
tmp = prei;
}
ans[cnt++] = i; //至此已求出i到j的上一个最短路的路径，路径是倒着存的
ans[cnt++] = k; //因为通过k松弛，所以要将k加入环
}
}
}
//求最短路及路径
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (disti + distk < disti)
{
disti = disti + distk;
prei = prek;
}
}
}
}
}
int main()
{
int u, v, w;
scanf("%d%d", &n, &m);
init();
for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &w);
if (distu > w)
{ //找最小环遇到平行边时取其最小边权
distu = distv = w;
mapu = mapv = w;
}
}
Floyd();
if (min_loop == INF)
printf("No solution");
else
{
for (int i = 0; i < cnt; i++)
printf("%d ", ans[i]);
printf("\n");
}
return 0;
}