弗洛伊德最短路徑演算法

『壹』 Floyd演算法與Dijkstra演算法的區別

1、如果依次對某個頂點運用Dijkstra演算法，則與Floyd演算法相比，很多路徑和結果計算是重復的，雖然復雜度相同，但是運算量差了很多；

2、更為重要的是：Dijkstra演算法使用的前提是圖中路徑長度必須大於等於0；

但是Floyd演算法則僅僅要求沒有總和小於0的環路就可以了，因此Floyd 演算法應用范圍比Dijkstra演算法要廣。

『貳』 Floyd演算法是什麼

Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。
通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。
從圖的帶權鄰接矩陣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)為圖的距離矩陣，同時還可引入一個後繼節點矩陣path來記錄兩點間的最短路徑。
採用的是(鬆弛技術)，對在i和j之間的所有其他點進行一次鬆弛。所以時間復雜度為O(n^3); 其狀態轉移方程如下： 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，或者按照題目意思來做。
當然，如果這條路沒有通的話，還必須特殊處理，比如沒有map[i,k]這條路

『叄』 最短路徑問題手抄報

最短路徑問題是組合優化領域的經典問題之一，它廣泛應用於計算機科學、交通工程、通信工程、系統工程、運籌學、>資訊理論、控制理論等眾多領域。>Dijkstra演算法是經典的最短路徑演算法。

一、相關演算法

1、Dijkstra演算法

Dijkstra演算法是經典的最短路徑演算法，其基本思想是:設置一個集合S存放已經找到最短路徑的頂點，S的初始狀態只包含源點v，對vi∈V-S，假設從源點v到vi的有向邊為最短路徑。以後每求得一條最短路徑v, …, vk，就將vk加入集合S中，並將路徑v, …, vk , vi與原來的假設相比較，取路徑長度較小者為最短路徑，重復上述過程，直到集合V中全部頂點加入到集合S中。使用該演算法找到的是全局最優的最短路徑，在網路節點數量大、網路邊數較多時，存在內存佔用大、時間復雜度高等不足，並且Dijkstra演算法不能很好地解決含必經點約束的最短路徑問題。

2、Floyd演算法

演算法的特點：

弗洛伊德演算法是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或有向圖或負權（但不可存在負權迴路)的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。

通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入兩個矩陣，矩陣S中的元素a[j]表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。矩陣P中的元素b[j]，表示頂點i到頂點j經過了b[j]記錄的值所表示的頂點。

假設圖G中頂點個數為N，則需要對矩陣D和矩陣P進行N次更新。初始時，矩陣D中頂點a[j]的距離為頂點i到頂點j的權值；如果i和j不相鄰，則a[j]=∞，矩陣P的值為頂點b[j]的j的值。 接下來開始，對矩陣D進行N次更新。第1次更新時，如果」a[j]的距離」 > 「a+a[j]」(a+a[j]表示」i與j之間經過第1個頂點的距離」)，則更新a[j]為」a+a[j]」,更新b[j]=b。 同理，第k次更新時，如果」a[j]的距離」 > 「a[k-1]+a[k-1][j]」，則更新a[j]為」a[k-1]+a[k-1][j]」,b[j]=b[k-1]。[1]

3、蟻群演算法

>蟻群演算法是由Dorigo、Maniezzo和Colorni等於1991 年首先提出來的，它來源於螞蟻尋食的行為。通過研究發現，螞蟻個體之間是通過一種叫做信息素的外激素進行信息傳遞的。螞蟻在行走過程中能感知周圍信息素的強度， 並朝著信息素濃度高的方向移動，當某隻螞蟻發現食物時，它在回巢的過程當中，會在返回的路上釋放信息素作為標記，同伴發現後會沿著此路尋找到食物。當同伴中多隻螞蟻都發現了食物但路徑長短不同時，因為螞蟻在短的路徑上往返所需要的時間相對較小，所以單位時間內走過的螞蟻越來越多，在這條路徑上的信息素濃度就會越強，因此，該路徑上的螞蟻就會越來越多，逐漸選出一條最優的道路。

二、分類

可分成兩個子問題，即單源最短路徑問題和所有頂點對之間的最短路徑問題。前者是找出從某一頂點出發到圖中所有其他頂點的最短路徑，主要演算法有迪克斯徹演算法等;後者是求圖中每一對頂點之間的最短路徑，主要演算法有弗洛伊德演算法等。

三、應用

1、通信領域

互聯網技術和應用的不斷發展，對當今網路通信流量的要求不斷增大。流量大、速度快、費用低的傳輸方式是網路傳輸的關鍵。路徑最短、代價最低的網路路由能夠大大降低通信成本、節約網路資源，提高網路資源的利用率。

2、交通運輸

最短路徑問題是交通分配中最基本的問題，是指一對節點之間的路徑中總阻 抗最小的路徑，幾乎所有交通流分配方法都是以它作為一個基本子過程反復調用。

『肆』 為什麼floyd演算法可以計算負權值圖的最短路徑問題

弗洛伊德演算法：Dis(i,j) =min(Dis(i,j), Dis(i,k) + Dis(k,j)).
我是這么理解的，Dis(i,k)或Dis(k,j)可以有一條邊是負的，只要兩者之和不是負的就行，因為兩個和為負就會選取到這個組合，但是路徑的結果不應該是負的。Dijkstra中S(已求出解)中的每一個點解即最短路徑是已求出的,若存在負數路徑,可能存在已求出的解不是最優解.

『伍』 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法

迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。

迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。

弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。

『陸』 用弗洛伊德演算法求最短路徑

是地信的題吧，先給你說v1怎麼求，
先找出v1能去的最近的點，為V2，
如果S1i>S12+S2i
修改V1到Vi的距離為S12+S2i
然後去掉V2，在其餘的點中找距V1最近的，按上面的方法修改
最後得到V1與其他各點的最短距離
同樣的方法求出到其他點的最短距離

『柒』 弗洛伊德演算法可以解決無向圖最短路徑么

可以的，弗洛伊德演算法利用動態規劃解決了無向圖中任意兩個點之間的最短路徑，時間復雜度是O(n^3)，n是圖中點個數
同時可以使用狄傑斯卡拉演算法解決無向圖的最短路徑問題，他計算的是圖中指定點到其餘各點的最短路徑，時間復雜度是O(n^2)

『捌』 求弗洛伊德演算法的詳細解釋~

floyd演算法思想：1，構建一個鄰接矩陣存儲任意兩點之間的權值如圖D0.

2、例如求v1,v4之間的最短路徑。先增加v2做中間頂點，D[1][4]=∞。if（D[1][4]>D[1][2]+D[2]4]）=6+4）D[1][4]=10;這樣就可以了。

3、如不能在離得較遠的兩點(例v1,v9）直接得到上述可以滿足if的中間點，則跟據你書本的代碼可以先構建原點到中間點的最短路徑，繼而就可以求得vi,v9之間的最短路徑

『玖』 每一對頂點之間的最短路徑是什麼

每一對頂點之間的最短路徑是指對於給定的帶權有向圖G＝（v，E），要對G中任意一對頂點有序對（vi，vj）（vi≠vj），找出vi到vj的最短距離和vj到vi的最短距離。

解決此問題的一個有效方法是：輪流以每一個頂點為源點，重復執行Dijkstra演算法n次，即可求得有向圖G＝（v，E）中每一對頂點間的最短路徑，總的時間復雜度為0（n2）。

弗洛伊德（Floyd）提出了另一個求任意兩頂點之間最短路徑的演算法，雖然其時間復雜度也是0（n2），但演算法形式更為簡明，易於理解與編程。

1.弗洛伊德演算法的思想弗洛伊德演算法是從圖的鄰接矩陣開始，按照頂點v0，v1，v2，v2，…，vn的次序，分別以每個頂點vk（0≤k＜n）作為新考慮的中間點，在第k－1次運算D（k－1）的基礎上，求出每一對頂點之間vi到vj的最短路徑長度D（k）［i］［j］，計算公式為：

D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝重復執行n次後，D（k）［i］［j］中保留的值就是每對頂點的vi到vj的最短路徑長度。

2.弗洛伊德演算法的步驟（1）從圖的帶權鄰接矩陣G．arcs［］［］開始，即D（－1）＝arcs［］［］，每次以上一次D（k－1）為基礎，用公式D（k）［i］［j］＝min｛D（k－1）［i］［j］，D（k－1）［i］［k］＋D（k－1）［k］［j］｝計算出D（k）［i］［j］的值，即D（k－1）［i］［k］＋D（k－1）［k］［j］＜D（k－1）［i］［j］才修改，若D（k）［i］［j］修改過，則相應的路徑P（k）［i］［j］也要作相應的修改，即P（k）［i］［j］＝P（k－1）［i］［k］＋P（k－1）［k］［j］。

（2）重復上述過程n次後，D（k）［i］［j］中保存的就是每一對頂點的最短路徑長度，P（k）［i］［j］中保存的就是每一對頂點的最短路徑。

說明：從計算公式可以看出，i＝j是對角線上的元素；i＝k是i行上的元素；j＝k是j列上的元素，這些特殊的頂點不用計算，保留原來的數據值。因此，計算的數據元素減少了很多。

『拾』 floyd演算法能不能保證有最優解

Floyd演算法又稱為弗洛伊德演算法，插點法，是一種用於尋找給定的加權圖中頂點間最短路徑的演算法。

演算法過程:

把圖用鄰接距陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。

定義一個距陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經過的點，初始化D[i,j]=j。
把各個頂點插入圖中，比較插點後的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。

在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。
比如，要尋找從V5到V1的路徑。根據D，假如D(5,1)=3則說明從V5到V1經過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。