圖 之 Floyd 算法

定義概覽

可以正确處理有向圖或負權的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。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=0; i<Graph->Nv; i++ )
        for( j=0; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }

    for( k=0; k<Graph->Nv; k++ )
        for( i=0; i<Graph->Nv; i++ )
            for( j=0; 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]<0 ) /* 若發現負值圈 */
                        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 = 1; k <= N; ++k){
        for(int i = 1; i <= N; ++i){
            for(int j = 1; 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 = 1 ; i <= N ; ++i){
        for(int j = 1; j <= N; ++j){
            if(i == j) floyd[i][j] = 0;
            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 = 1; 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 = 1;
    for(int i = 1; i<= N; ++i){
        int maxTemp = 0;
        for(int j = 1; 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 0;
}