1. 算法簡介

弗洛伊德算法與迪杰斯特拉算法是公認的最著名的兩種最短路徑求解算法，接下來介紹弗洛伊德算法，弗洛伊德算法的思路是：首先初始化距離矩陣，然后從第一個點開始逐漸更新矩陣點值。d[i][j]表示從i點到j點的距離。第k次更新時，判斷d[i][k]+d[k][j]與d[i][j]的大小，如果前者小，則更新這個值，否則不變。

這個算法的核心點在于去往每一個點我們所要盡力的每一個點的記錄

(參考圖，試著拿本圖進行一次構建吧)

2.算法實現(xiàn)：

通過一個圖的權值矩陣求出它的每兩點間的最短距離矩陣。

從圖的帶權鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；……；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。

采用松弛技術（松弛操作），對在i和j之間的所有其他點進行一次松弛。所以時間復雜度為O(n^3);

狀態(tài)轉(zhuǎn)移方程

其狀態(tài)轉(zhuǎn)移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；

map[i,j]表示i到j的最短距離，K是窮舉i,j的斷點，map[n,n]初值應該為0或者自定義的特殊意義的點

3. 代碼實現(xiàn)

參考代碼，簡化了輸入操作直接賦值。

#include <stdio.h>
#include <stdlib.h>
 
#define MAXVEX 9
#define INFINITY 65535
 
struct MGraph {
    int numVertexes;
    int *vex;
    int arc[MAXVEX][MAXVEX];
};
 
typedef int PathMatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
 
void ShortestPath_Floyd(MGraph *G,PathMatrix *P,ShortPathTable *D) {
    int v,w,k;
    //初始化
    for(v=0; v<G->numVertexes; ++v) {
        for(w=0; w<G->numVertexes; ++w) {
            (*D)[v][w]=G->arc[v][w];
            (*P)[v][w]=w;
        }
    }
 
    for(k=0; k<G->numVertexes; ++k) {
        for(v=0; v<G->numVertexes; ++v) {
            for(w=0; w<G->numVertexes; ++w) {
                if( (*D)[v][w]>(*D)[v][k]+(*D)[k][w] ) { // (v到w的距離) VS (v到k的距離+k到w的距離)
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
                    (*P)[v][w]=(*P)[v][k]; //若從v出發(fā)，要去w，則先要從v去到k，“再作下一步打算(下一步即(*P)[k][w])”
                }
            }
        }
    }
}
 
void main() {
    MGraph *my_g=(struct MGraph*)malloc(sizeof(struct MGraph));
    int i,j;
    int t=0;
 
    int v0=0;
    int vv=8;
 
    my_g->numVertexes=MAXVEX;
    my_g->vex=(int*)malloc(sizeof(char)*my_g->numVertexes);
    if(!my_g->vex) return;
    for(i=0; i<my_g->numVertexes; ++i) //一維數(shù)組(圖中各結點)初始化{0,1,2,3,4,5,6,7,8}
        my_g->vex[i]=i++;
 
    for(i=0; i<my_g->numVertexes; ++i)
        for(j=0; j<my_g->numVertexes; ++j)
            my_g->arc[i][j]=INFINITY;
 
    // 無向圖的權值二維數(shù)組為對稱矩陣
    my_g->arc[0][1]=1;
    my_g->arc[0][2]=5;
    my_g->arc[1][2]=3;
    my_g->arc[1][3]=7;
    my_g->arc[1][4]=5;
    my_g->arc[2][4]=1;
    my_g->arc[2][5]=7;
    my_g->arc[3][4]=2;
    my_g->arc[3][6]=3;
    my_g->arc[4][5]=3;
    my_g->arc[4][6]=6;
    my_g->arc[4][7]=9;
    my_g->arc[5][7]=5;
    my_g->arc[6][7]=2;
    my_g->arc[6][8]=7;
    my_g->arc[7][8]=4;
    for(i=0; i<my_g->numVertexes; ++i)
        for(j=0; j<=i; ++j) {
            if(i==j) {
                my_g->arc[i][j]=0;
                continue;
            }
            my_g->arc[i][j]=my_g->arc[j][i];
        }
    for(i=0; i<my_g->numVertexes; ++i) { //二維數(shù)組表示圖中各結點間連接邊的weight
        for(j=0; j<my_g->numVertexes; ++j)
            printf("%5d  ",my_g->arc[i][j]);
        printf("\n");
    }
    printf("\n\n");
 
    PathMatrix D;
    ShortPathTable P;
    ShortestPath_Floyd(my_g,&P,&D);
    for(i=0; i<MAXVEX; ++i) { //二維數(shù)組表示圖中各結點間連接邊的weight
        for(j=0; j<MAXVEX; ++j)
            printf("%5d  ",P[i][j]);
        printf("\n");
    }
    printf("\n\n");
 
    free(my_g->vex);
}