任意两点间的最短路径

任意两点间的最短路径
用floyd算法

void floyd(){
    for(int k=1;k<=N;++k){
        for(int i=1;i<=N;++i){
            for(int j=1;j<=N;++j){
                if( dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pos[i][j] = k;//如果需要记录i,j中间经过哪些点，组成最短路
                }
            }
        }
    }
}
//获取路径
void genPath(int i,int j){
    int k = pos[i][j];
    if ( k == 0 ) return;
    genPath(i,k);
    p.push_back(k);
    genPath(k,j);
}

最小环
最小环即最少三个点组成的一个环，最小。
算法是，寻找i,j,k 三个点，其中，i,j 为最短路径，i,k和k,j 为原始路径 ( 我不知道为什么这样可以找到)

void findMinPath(){
    int minP = INT_MAX;
    for(int k=1;k<=N;++k){
        for(int i=1;i<k;++i){
            for(int j=1;j<i;++j){
                minP = min(minP, dist[i][j] + g[k][i] + g[j][k]);
            }
        }
        for(int i=1;i<=N;++i){
            for(int j=1;j<=N;++j){
                if( dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}