1. 首页
2. 最短路
3. 本页

Floyd求最小环

算法引入：

*求一个图G中的最小环路的朴素算法为:每次找到一条边,删除了求这两点之间的最短路径;

*若能求出,则这条最短路径与原来的边构成一个环,不过时间复杂度略高;

*算法思想;

*Floyd算法是按照顶点的编号增加的顺序更新最短路径的;

*如果存在最小环,则会在这个环中的点编号最大的那个点u更新最短路径之前发现这个环;

*即当点u被拿来更新i到j的最短路径的时候,可以发现这个闭合环路;

*发现的方法是,更新最短路径前,遍历i,j点对,一定会发现某对i到j的最短路径长度:

*dist[i][j]+map[j][u]+map[u][i]!=INF,这时s的i和j是当前环中挨着点u的两个点;

*因为在之前的最短路径更新过程中,u没有参与更新,所以dist[i][j]所表示的路径中不会有点u,即一定为一个环;

*

*如果在每个新的点拿来更新最短路径之前遍历i和j验证上面的式子,虽然不能遍历到所有的环;

*但是由于dist[i][j]是i到j点的最短路径m所以肯定可以遍历到最小的环;

*

*如果有负权环,则该算法失效,因为包含负环的图上,dist[i][j]已经不能保证i到j的路径上不会经过同一个点多次了;

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int g[155][155], dis[155][155];
LL ans;
void floyd(int n)
{
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 1; i <= k - 1; ++i)
            for(int j = i + 1; j <= k - 1; ++j)
                if(ans > g[i][j] + dis[i][k] + dis[k][j]) ans = (LL)g[i][j] + dis[i][k] + dis[k][j];
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n ; ++j)
                if(g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    while(cin >> n >> m)
    {
        memset(g, 0x3f3f3f3f, sizeof(g));
        memset(dis, 0x3f3f3f3f, sizeof(dis));
        for(int i = 0; i < m; ++i)
        {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = g[v][u] = dis[u][v] = dis[v][u] =w;
        }
        ans = 0x3f3f3f3f;
        floyd(n);
        if(ans == 0x3f3f3f3f) cout << "No solution." << endl;
        else cout << ans << endl;
    }

    return 0;
}