目錄

簡(jiǎn)介

核心思路

優(yōu)缺點(diǎn)分析

算法過程

? ? ? ? ?示例

簡(jiǎn)介

Floyd算法又稱為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創(chuàng)始人之一、1978年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名。

核心思路

路徑矩陣

通過一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣。?[3]?

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

采用松弛技術(shù)（松弛操作），對(duì)在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時(shí)間復(fù)雜度為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(luò)的最短距離，K是窮舉i,j的斷點(diǎn)，map[n,n]初值應(yīng)該為0，或者按照題目意思來(lái)做。

當(dāng)然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路。

優(yōu)缺點(diǎn)分析

編輯?語(yǔ)音

Floyd算法適用于APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡(jiǎn)單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對(duì)于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法，也要高于執(zhí)行|V|次SPFA算法。

優(yōu)點(diǎn)：容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡(jiǎn)單。

缺點(diǎn)：時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)

算法過程

?在Floyd算中一般會(huì)用到有兩個(gè)矩陣，一個(gè)距離矩陣D，一個(gè)路由矩陣R，顧名思義距離矩陣D是用來(lái)儲(chǔ)存任意兩點(diǎn)之間的距離的，而路由矩陣則是用來(lái)記錄任意兩點(diǎn)之間的路徑關(guān)系。??

Floyd算法的原理是：對(duì)于每一對(duì)頂點(diǎn) i?和 j，看看是否存在一個(gè)頂點(diǎn) w 使得從 i 到 w 再到 j?比已知的路徑更短。如果是更新它。

把圖用鄰接矩陣r表示出來(lái)，如果從Vi到Vj有路可達(dá)，則D[i，j]=d(在矩陣D中為具體的數(shù)字)，d表示該路的長(zhǎng)度；否則D[i，j]=無(wú)窮大（在矩陣D中用“inf“表示）。定義一個(gè)矩陣D用來(lái)記錄所插入點(diǎn)的信息，R[I,j]表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化R[i,j]=j（即先默認(rèn)i到j(luò)是通的）。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來(lái)的距離，假設(shè)插入的中間點(diǎn)為k，D[i,j] >?D[i,k]+D[k,j] )，此時(shí)證明從i點(diǎn)經(jīng)過k點(diǎn)再到j(luò)點(diǎn)比原來(lái)的要短，所以此時(shí)要更新D[i,j],則D[i,j]=D[I,k]+[k,j],同時(shí)此時(shí)R[i,j]=k。在R中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。

可能有些人對(duì)路由矩陣R不是很明白，其實(shí)路由矩陣R很好理解，我來(lái)舉個(gè)例子，

比如，要尋找從V5到V1的路徑。根據(jù)R，假如 R(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為{V5,V3,V1}，如果R(5,3)=3，說明V5與V3直接相連，如果R(3,1)=1，說明V3與V1直接相連。

因此，我們?cè)诙x路由矩陣R時(shí)，先要初始化矩陣（即先默認(rèn)任意兩點(diǎn)是相互相通的），即每列上的數(shù)等于該列的列序數(shù)。

例：

示例

下面我將用一個(gè)簡(jiǎn)單的例子來(lái)說明，下面是一個(gè)簡(jiǎn)單的例子：

問題：求出任意兩點(diǎn)間的最短距離及其路徑？

我們此時(shí)可以寫出距離矩陣D和路由矩陣R如下：

?

這樣我們就定義好了距離矩陣和路由矩陣，現(xiàn)在我們?cè)賮?lái)假設(shè)圖中任意兩點(diǎn)之間都要經(jīng)V5這個(gè)點(diǎn)中轉(zhuǎn)。算出經(jīng)過中轉(zhuǎn)后的兩點(diǎn)之間的距離，然后我們?cè)賮?lái)判斷任意兩點(diǎn)之間的最短距離。
（1）先從V5開始，先讓V5成為中轉(zhuǎn)點(diǎn)。

V5由V5中轉(zhuǎn)，那么V5到到各個(gè)點(diǎn)的距離還是不變。

V4可以經(jīng)由V5中轉(zhuǎn)，那么這個(gè)時(shí)候判斷一下中轉(zhuǎn)前和中轉(zhuǎn)后的距離大小，將最小距離留存下來(lái)如：

V4>V3?經(jīng)V5中轉(zhuǎn)，原來(lái)V4->V3?= inf，經(jīng)由V5中轉(zhuǎn)之后V4->V5->V3?= 17, 于是V4到V3的最短距離變化為17，更新距離矩陣D(4,3)=17,更新路由矩陣R(4,3) = R(4,5) = 5

V1、V2、V3沒有到達(dá)V5的路徑，所以也就不存在從V5中轉(zhuǎn)的情況，所以V1、V2、V3到各個(gè)點(diǎn)的距離還是不變。

這時(shí)兩個(gè)矩陣變化為

?

（2）再讓V4成為中轉(zhuǎn)點(diǎn)。

V5 ?V1 都沒有到達(dá)V4的路徑，所以也就不存在從V5中轉(zhuǎn)的情況，所以V5 V1 到各個(gè)點(diǎn)的距離還是不變。

V2>V5?經(jīng)V4中轉(zhuǎn)，原來(lái)V2->V5?= inf，經(jīng)由V4中轉(zhuǎn)之后V2->V4->V5?= 15, 于是V2到V5的最短距離變化為15，更新距離矩陣D(2,5)=15,更新路由矩陣R(2,5) = R(2,4) = 4

V3>V2經(jīng)V4中轉(zhuǎn)，原來(lái)V3->V2= inf，經(jīng)由V4中轉(zhuǎn)之后V3->V4->V2?= 5, 于是V3到V2的最短距離變化為5，更新距離矩陣D(3,2)=5,更新路由矩陣R(3,2) = R(3,4) = 4

V3>V5?經(jīng)V4中轉(zhuǎn)，原來(lái)V3->V5?= 6，經(jīng)由V4中轉(zhuǎn)之后V3>V4->V5?= 11, 因此V3到V5的最短距離仍為6，不更新。

這時(shí)兩個(gè)矩陣變化為

?(3)同理，讓所有的點(diǎn)都成為一次中轉(zhuǎn)點(diǎn)

用Matlab來(lái)表示上面的過程，其代碼為：

（1）先建立一個(gè).m文件

function [d,r]=floyd(a)
n=size(a,1);%測(cè)出a矩陣的行數(shù)
d=a;% 初始化距離矩陣
for i=1:n % 初始化路由矩陣
    for j=1:n
        r(i,j)=j;%使路由矩陣r形成初始矩陣（每一列上的數(shù)為該列的列序數(shù)，例：第3列上的數(shù)全為3）（上面有提到）
    end 
end 
r;

for k=1:n % 開始Floyd算法（用if語(yǔ)句來(lái)比較中轉(zhuǎn)前后的大?。?    for i=1:n
        for j=1:n
            if d(i,k)+d(k,j)<d(i,j)%需要更新的條件（也就是中轉(zhuǎn)后比原來(lái)要?。?                d(i,j)=d(i,k)+d(k,j);
                r(i,j)=r(i,k);
            end 
        end 
    end
    k;
    d;
    r;

?(2)在命令行輸入矩陣a，也就是距離矩陣

> a=[0 inf 5 inf inf;
      4 0 inf 6 inf ;
      inf inf 0 2 6;
     inf 3 inf 0 9;
     inf inf 8 inf 0];
>> [d,r]=floyd(a)

（3）得出距離矩陣D和路由矩陣R?

（4）怎么通過得出的這兩個(gè)矩陣看任意一點(diǎn)到任意一點(diǎn)的最短距離及其路徑。

從任意一點(diǎn)到任意一點(diǎn)從矩陣d中就很容易看出來(lái)了，比如D(2,3)=9,就表示V2到V3的最短距離是9，因此兩點(diǎn)的距離從矩陣中很容易看出，我就不過多解釋了。

現(xiàn)在我重點(diǎn)來(lái)說一下怎么看路由矩陣：

舉個(gè)例子：v4->V3

從距離矩陣中可以看出V4->V3的最短距離是D(4,3) = 12；根據(jù)其路由矩陣我們可以看出：

R(4,3) = 2,表示V4->V3,先經(jīng)過V2，于是再看R(2,3) = 1,表示還需要再經(jīng)過V1,于是我們看R(1,3) = 3,這個(gè)時(shí)候我們發(fā)現(xiàn)終于到了V3,所以我們梳理一下，V4->V3的最短路徑是：V4->V2->V1->V3。簡(jiǎn)言之就是固定列，根據(jù)路由矩陣在行中跳轉(zhuǎn)，直到跳轉(zhuǎn)到對(duì)應(yīng)的點(diǎn)。

再來(lái)個(gè)例子：v5->V2

從距離矩陣中可以看出V5->V2的最短距離是D(5,2) = 13；根據(jù)其路由矩陣我們可以看出：

R(5,2) = 3,表示V5->V2,先經(jīng)過V3，于是再看R(3,2) = 4,表示還需要再經(jīng)過V4,于是我們看R(4,2) = 2,這個(gè)時(shí)候我們發(fā)現(xiàn)終于到了V2,所以V5->V2的最短路徑是：V4->V2->V1->V3。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-449279.html

此時(shí)我們已經(jīng)拿到了我們最開始想要的結(jié)果了?。?！

到了這里，關(guān)于最短路徑-任意兩點(diǎn)間最短距離-Floyd算法的matlab實(shí)現(xiàn)（詳細(xì)教程）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！