图 之 Floyd 算法

定义概览

　　Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。

我的看法

　　找i 到 j 的最短路径， 加入若干个k 若 i 到 k - k 到 j 的路径更短， 则更新；反之继续

　　　　①初始化D[i][j] 对角线初始化为0

　　　 ②若两个顶点有邻边则加上权值

　　　 ③若两个顶点无连边则赋值为+无穷

/* 邻接矩阵存储 - 多源最短路算法 */

bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    Vertex i, j, k;

    /* 初始化 */
    for ( i=; i<Graph->Nv; i++ )
        for( j=; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -;
        }

    for( k=; k<Graph->Nv; k++ )
        for( i=; i<Graph->Nv; i++ )
            for( j=; j<Graph->Nv; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
                    if ( i==j && D[i][j]< ) /* 若发现负值圈 */
                        return false; /* 不能正确解决，返回错误标记 */
                    path[i][j] = k;
                }
    return true; /* 算法执行完毕，返回正确标记 */
}
           

题目链接：https://pta.patest.cn/pta/test/1342/exam/4/question/23158

题意：

　　无相有权图，找到顶点到顶点的最小边即可。

代码如下：

#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 105
#define MAXN_LEN 10005
using namespace std;
int floyd[MAXN][MAXN];

int N, M;   //N 为 动物总数 ； M 为咒语总数

void Floyd(){
    for(int k = ; k <= N; ++k){
        for(int i = ; i <= N; ++i){
            for(int j = ; j <= N; ++j){
                if(floyd[i][k] + floyd[k][j] < floyd[i][j])
                    floyd[i][j] = floyd[i][k] + floyd[k][j];
            }
        }
    }
}

void init(){
    for(int i =  ; i <= N ; ++i){
        for(int j = ; j <= N; ++j){
            if(i == j) floyd[i][j] = ;
            else floyd[i][j] = MAXN_LEN;
        }
    }
}

int main(void){
    scanf("%d%d", &N, &M);
    init(); // 初始化floyd

//    for(int i = 1; i <= N; ++i){
//        for(int j = 1; j <= N; ++j){
//            printf("%d ", floyd[i][j]);
//        }
//        printf("\n");
//    }

    int n1, n2, weight;
    for(int i = ; i <= M ; ++i){
        scanf("%d%d%d", &n1, &n2, &weight);
//        pic[n1][n2] = weight;
//        pic[n2][n1] = weight;
        floyd[n1][n2] = weight;
        floyd[n2][n1] = weight;
    }
    Floyd();
    int Min = MAXN_LEN;
    int Tag = ;
    for(int i = ; i<= N; ++i){
        int maxTemp = ;
        for(int j = ; j <= N; ++j){
            if(floyd[i][j] > maxTemp)
                maxTemp = floyd[i][j];
        }
        if(maxTemp < Min){
            Tag = i;
            Min = maxTemp;
        }
    }

//    for(int i = 1; i <= N; ++i){
//        for(int j = 1; j <= N; ++j){
//            printf("%d ", floyd[i][j]);
//        }
//        printf("\n");
//    }

    if(Min == MAXN_LEN)
        printf("0");
    else
        printf("%d %d", Tag, Min);
    return ;
}