• 用來(lái)求圖中所有點(diǎn)對(duì)之間的最短路徑
• Dijkstra算法是求單源最短路徑的桐玻，那如果求圖中所有點(diǎn)對(duì)的最短路徑的話則有以下兩種解法：
  • 解法一：
    以圖中的每個(gè)頂點(diǎn)作為源點(diǎn)，調(diào)用Dijkstra算法宏多，時(shí)間復(fù)雜度為O(n3)萧求；
  • 解法二：
    Floyd（弗洛伊德算法）更簡(jiǎn)潔腕巡，算法復(fù)雜度仍為O(n3)俊卤。
• 正如大多數(shù)教材中所講到的嫩挤，求單源點(diǎn)無(wú)負(fù)邊最短路徑用Dijkstra，而求所有點(diǎn)最短路徑用Floyd消恍。確實(shí)岂昭，我們將用到Floyd算法，但是狠怨，并不是說(shuō)所有情況下Floyd都是最佳選擇约啊。
• 對(duì)于沒(méi)有學(xué)過(guò)Floyd的人來(lái)說(shuō)，在掌握了Dijkstra之后遇到All-Pairs最短路徑問(wèn)題的第一反應(yīng)可能會(huì)是：計(jì)算所有點(diǎn)的單源點(diǎn)最短路徑佣赖，不就可以得到所有點(diǎn)的最短路徑了嗎恰矩。簡(jiǎn)單得描述一下算法就是執(zhí)行n次Dijkstra算法。
• Floyd可以說(shuō)是Warshall算法的擴(kuò)展了憎蛤，三個(gè)for循環(huán)便可以解決一個(gè)復(fù)雜的問(wèn)題外傅，應(yīng)該說(shuō)是十分經(jīng)典的。從它的三層循環(huán)可以看出蹂午，它的復(fù)雜度是n3栏豺，除了在第二層for中加點(diǎn)判斷可以略微提高效率，幾乎沒(méi)有其他辦法再減少它的復(fù)雜度豆胸。
• 比較兩種算法奥洼，不難得出以下的結(jié)論：對(duì)于稀疏的圖，采用n次Dijkstra比較出色晚胡，對(duì)于茂密的圖灵奖，可以使用Floyd算法。另外估盘，F(xiàn)loyd可以處理帶負(fù)邊的圖瓷患。

下面對(duì)Floyd算法進(jìn)行介紹：

• Floyd算法的基本思想：
  可以將問(wèn)題分解:
  第一、先找出最短的距離
  第二遣妥、然后在考慮如何找出對(duì)應(yīng)的行進(jìn)路線擅编。
  如何找出最短路徑呢，這里還是用到動(dòng)態(tài)規(guī)劃的知識(shí)箫踩，對(duì)于任何一個(gè)城市而言爱态，i到j(luò)的最短距離不外乎存在經(jīng)過(guò)i與j之間經(jīng)過(guò)k和不經(jīng)過(guò)k兩種可能，所以可以令k=1境钟，2锦担，3，...慨削，n(n是城市的數(shù)目)洞渔，在檢查d(ij)與d(ik)+d(kj)的值套媚；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j(luò)的最短距離，因此d(ik)+d(kj)就是i到j(luò)經(jīng)過(guò)k的最短距離磁椒。所以堤瘤，若有d(ij)>d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過(guò)k再到j(luò)的距離要比原來(lái)的i到j(luò)距離短衷快，自然把i到j(luò)的d(ij)重寫(xiě)為d(ik)+d(kj)宙橱，每當(dāng)一個(gè)k查完了姨俩，d(ij)就是目前的i到j(luò)的最短距離蘸拔。重復(fù)這一過(guò)程，最后當(dāng)查完所有的k時(shí)环葵，d(ij)里面存放的就是i到j(luò)之間的最短距離了调窍。

Floyd算法的基本步驟：

• 定義n×n的方陣序列D-1, D0 , … Dn－1,

• 初始化： D-1＝C

  • D-1[i][j]＝邊<i,j>的長(zhǎng)度，表示初始的從i到j(luò)的最短路徑長(zhǎng)度张遭，即它是從i到j(luò)的中間不經(jīng)過(guò)其他中間點(diǎn)的最短路徑邓萨。

• 迭代：設(shè)Dk-1已求出，如何得到Dk（0≤k≤n-1）菊卷？

  • Dk-1[i][j]表示從i到j(luò)的中間點(diǎn)不大于k-1的最短路徑p：i…j缔恳，
  • 考慮將頂點(diǎn)k加入路徑p得到頂點(diǎn)序列q：i…k…j，
  • 若q不是路徑洁闰，則當(dāng)前的最短路徑仍是上一步結(jié)果：Dk[i][j]= Dk－1[i][j]歉甚；
  • 否則若q的長(zhǎng)度小于p的長(zhǎng)度，則用q取代p作為從i到j(luò)的最短路徑

• 因?yàn)閝的兩條子路徑i…k和k…j皆是中間點(diǎn)不大于k－1的最短路徑扑眉，所以從i到j(luò)中間點(diǎn)不大于k的最短路徑長(zhǎng)度為：
  Dk[i][j]＝min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }

Floyd算法實(shí)現(xiàn)：

• 可以用三個(gè)for循環(huán)把問(wèn)題搞定了纸泄，但是有一個(gè)問(wèn)題需要注意，那就是for循環(huán)的嵌套的順序：我們可能隨手就會(huì)寫(xiě)出這樣的程序腰素，但是仔細(xì)考慮的話聘裁，會(huì)發(fā)現(xiàn)是有問(wèn)題的。
  for(int i=0; i<n; i++)
  for(int j=0; j<n; j++)
  for(int k=0; k<n; k++)

• 問(wèn)題出在我們太早的把i-k-j的距離確定下來(lái)了弓千，假設(shè)一旦找到了i-p-j最短的距離后衡便，i到j(luò)就相當(dāng)處理完了，以后不會(huì)在改變了洋访，一旦以后有使i到j(luò)的更短的距離時(shí)也不能再去更新了镣陕，所以結(jié)果一定是不對(duì)的。所以應(yīng)當(dāng)象下面一樣來(lái)寫(xiě)程序：
  for(int k=0; k<n; k++)
  for(int i=0; i<n; i++)
  for(int j=0; j<n; j++)

• 這樣做的意義在于固定了k捌显，把所有i到j(luò)而經(jīng)過(guò)k的距離找出來(lái)茁彭，然后象開(kāi)頭所提到的那樣進(jìn)行比較和重寫(xiě)，因?yàn)閗是在最外層的扶歪，所以會(huì)把所有的i到j(luò)都處理完后理肺，才會(huì)移動(dòng)到下一個(gè)k摄闸，這樣就不會(huì)有問(wèn)題了，看來(lái)多層循環(huán)的時(shí)候妹萨，我們一定要當(dāng)心年枕，否則很容易就弄錯(cuò)了。

路徑查找

• 接下來(lái)就要看一看如何找出最短路徑所行經(jīng)的城市了乎完，這里要用到另一個(gè)矩陣P熏兄，它的定義是這樣的：p(ij)的值如果為p，就表示i到j(luò)的最短行經(jīng)為i->...->p->j树姨，也就是說(shuō)p是i到j(luò)的最短行徑中的j之前的最后一個(gè)城市摩桶。P矩陣的初值為p(ij)=i。有了這個(gè)矩陣之后帽揪，要找最短路徑就輕而易舉了硝清。對(duì)于i到j(luò)而言找出p(ij)，令為p转晰，就知道了路徑i->...->p->j芦拿；再去找p(ip)，如果值為q查邢，i到p的最短路徑為i->...->q->p蔗崎；再去找p(iq)，如果值為r扰藕，i到q的最短路徑為i->...->r->q缓苛；所以一再反復(fù)，到了某個(gè)p(it)的值為i時(shí)实胸，就表示i到t的最短路徑為i->t他嫡，就會(huì)的到答案了，i到j(luò)的最短行徑為i->t->...->q->p->j庐完。因?yàn)樯鲜龅乃惴ㄊ菑慕K點(diǎn)到起點(diǎn)的順序找出來(lái)的钢属，所以輸出的時(shí)候要把它倒過(guò)來(lái)。
• 但是门躯，如何動(dòng)態(tài)的回填P矩陣的值呢淆党？回想一下，當(dāng)d(ij)>d(ik)+d(kj)時(shí)讶凉，就要讓i到j(luò)的最短路徑改為走i->...->k->...->j這一條路染乌，但是d(kj)的值是已知的，換句話說(shuō)懂讯，就是k->...->j這條路是已知的荷憋，所以k->...->j這條路上j的上一個(gè)城市(即p(kj))也是已知的，當(dāng)然褐望，因?yàn)橐淖遡->...->k->...->j這一條路勒庄，j的上一個(gè)城市正好是p(kj)串前。所以一旦發(fā)現(xiàn)d(ij)>d(ik)+d(kj)，就把p(kj)存入p(ij)实蔽。

小例子

• 代碼

#include<iostream>
#include<string.h>
using namespace std;

#define len 100
#define INF 999999

class Graph{
    // 內(nèi)部類
    private:
        // 鄰接表中表對(duì)應(yīng)的鏈表的頂點(diǎn)
        class ENode{
            public:
                int vex;         // 頂點(diǎn)
                int weight;      // 權(quán)重 
                ENode *nextEdge; // 指向下一條弧
        };

        // 鄰接表中表的頂點(diǎn)
        class VNode{
            public:
                char data; // 頂點(diǎn)信息
                ENode *firstEdge; // 指向第一條依付該頂點(diǎn)的弧
        };

    // 私有成員
    private:
        int n;              // 節(jié)點(diǎn)個(gè)數(shù) 
        int e;              // 邊的個(gè)數(shù)
        VNode mVexs[len];
    
    public:
        Graph(){
            ENode *node1, *node2;
            n = 7; 
            e = 12;

            // 設(shè)置節(jié)點(diǎn)為默認(rèn)數(shù)值
            string nodes = "ABCDEFG";
            // 輸入節(jié)點(diǎn)
            for(int i=0; i < n; i++){
                mVexs[i].data = nodes[i];
                mVexs[i].firstEdge = NULL;
            }

            // 設(shè)置邊為默認(rèn)值
            char edges[][2] = {
                {'A', 'B'}, 
                {'A', 'F'}, 
                {'A', 'G'}, 
                {'B', 'C'}, 
                {'B', 'F'}, 
                {'C', 'D'}, 
                {'C', 'E'},
                {'C', 'F'}, 
                {'D', 'E'},
                {'E', 'F'}, 
                {'E', 'G'},
                {'F', 'G'}
            };
            
            // 邊的權(quán)重
            int weights[len] = {12, 16, 14, 10, 7, 3, 5, 6, 4, 2, 8, 9};
            
            //　初始化鄰接表的邊
            for(int i=0; i < e; i++){
                int start = get_Node_Index(edges[i][0]);
                int end = get_Node_Index(edges[i][1]);

                // 初始化 node1
                node1 = new ENode();
                node1->vex = end;
                node1->weight = weights[i];
                node1->nextEdge = NULL;
                // 將 node 添加到 start 所在鏈表的末尾
                if(mVexs[start].firstEdge == NULL){
                    mVexs[start].firstEdge = node1;
                }
                else{
                    linkLast(mVexs[start].firstEdge, node1);
                }

                // 初始化 node2
                node2 = new ENode();
                node2->vex = start;
                node2->weight = weights[i];
                node2->nextEdge = NULL;
                // 將 node 添加到 end 所在鏈表的末尾
                if(mVexs[end].firstEdge == NULL){
                    mVexs[end].firstEdge = node2;
                }
                else{
                    linkLast(mVexs[end].firstEdge, node2);
                }
            }
        }

        // 相鄰節(jié)點(diǎn)鏈接子函數(shù)
        void linkLast(ENode*p1, ENode*p2){
            ENode*p = p1;
            while(p->nextEdge){
                p = p->nextEdge;
            }
            p->nextEdge = p2;
        }
        
        // 返回頂點(diǎn)下標(biāo)
        int get_Node_Index(char number){
            for(int i=0; i < n; i++){
                if(number == mVexs[i].data){
                    return i;
                }
            }
            return -1; //這句話永遠(yuǎn)不會(huì)執(zhí)行的
        }

        // 輸出鄰接表
        void print(){
            for(int i=0; i < n; i ++){
                cout<<mVexs[i].data;
                ENode *temp = mVexs[i].firstEdge;
                while(temp){
                    cout<<" -> "<<temp->vex;
                    temp = temp->nextEdge;
                }
                cout<<endl;
            }
            cout<<endl;
        }

        // 得到兩個(gè)節(jié)點(diǎn)之間的權(quán)重
        int getWeight(int m, int n){
            ENode *enode = mVexs[m].firstEdge;
            while(enode){
                if(enode->vex == n){
                    return enode->weight;
                }
                enode = enode->nextEdge;
            }
            return INF;
        }

        // 弗洛伊德算法
        void floyd(){
            int dist[n][n]; // 距離矩陣
            int path[7][7]; // 路徑矩陣, 7為節(jié)點(diǎn)數(shù)目
            int i, j, k;
            int temp;

            // 初始化權(quán)重
            for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                    if(i == j){
                        dist[i][j] = 0;
                    }
                    else{
                        dist[i][j] = getWeight(i, j);
                    }
                    path[i][j] = i;
                }
            }
            
            // floyd 算法開(kāi)始
            for(k = 0; k < n; k++){
                for(i = 0; i < n; i++){
                    for(j = 0; j < n; j++){
                        temp = (dist[i][k] == INF || dist[k][j] == INF)? INF : (dist[i][k] + dist[k][j]);
                        if(temp < dist[i][j]){
                            dist[i][j] = temp;
                            path[i][j] = path[k][j];
                        }
                    }
                }
            }

            // 打印出兩點(diǎn)之間最短距離 + 路徑
            for(i = 0; i < n-1; i++){
                for(j = i+1; j < n; j++){
                    if(dist[i][j] < 10){
                        cout<<mVexs[i].data<<" -> "<<mVexs[j].data<<": "<<dist[i][j]<<"  , 路徑為: ";
                    }
                    else{
                        cout<<mVexs[i].data<<" -> "<<mVexs[j].data<<": "<<dist[i][j]<<" , 路徑為: ";
                    }
                    getPath(i, j, path);
                    cout<<endl;
                }
                cout<<endl;
            }
            
            // 輸出路徑矩陣觀察, 可用此矩陣自己用筆演算一下路徑查找過(guò)程
            // for(i = 0; i < n; i++){
            //     for(j = 0; j < n; j++){
            //         cout<<path[i][j]<<" ";
            //     }
            //     cout<<endl;
            // }
        }

        // 遞歸實(shí)現(xiàn)得到節(jié)點(diǎn)之間最短路徑
        void getPath(int start, int end, int path[][7]){
            if(path[start][end] == start){
                cout<<mVexs[start].data<<" "<<mVexs[end].data<<" ";
            }
            else{
                getPath(start, path[start][end], path);
                cout<<mVexs[end].data<<" ";
            }
        }
};

int main(){
    Graph g;
    // 輸出鄰接表
    // g.print();

    // 弗洛伊德算法
    g.floyd();
    return 0;
}

參考

• Floyd算法(二)之 C++詳解