弗洛伊演算法

㈠ 求弗洛伊德演算法的詳細解釋~

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是求任意兩點之間的最短距離。要經過所有點的話可以用蟻群演算法，模擬退火演算法，遺傳演算法。

㈣ matlab實現弗洛伊德演算法的代碼，。

function
[d,r]=floyd(a)
%floyd.m
%採用floyd演算法計算圖a中每對頂點最短路
%d是矩離矩陣
%r是路由矩陣
n=size(a,1);
d=a;
for
i=1:n
for
j=1:n
r(i,j)=j;
end
end
r
for
k=1:n
for
i=1:n
for
j=1:n
if
d(i,k)+d(k,j)

評論
0

0

0

載入更多

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

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

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

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

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

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

㈦ 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直接相連。

㈧ 弗洛伊德演算法求出最短距離

（1）利用二維數組dist[i][j]記錄當前vi到vj的最短路徑長度，數組dist的初值等於圖的帶權鄰接矩陣;

（3）依次向S中加入v0,v1…vn-1，每加入一個頂點，蠢脊對dist[i][j]進行一次修正：設S={v0,v1…vk-1}，加入vk，則dist(k)[i][j]=min{dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含義：允許中間頂點的笑跡序號最大為k時從vi到vj的最短路徑長度。
dist(n-1)[i][j]就是vi到vj的最短路徑長度。

弗洛伊德最短距離演算法（FloydShortestPathAlgorithm）又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的演算法。該演算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
中文名弗洛伊德最短距離演算法
外文名FloydShortestPathAlgorithm
所屬學科IT
所屬領域程序設計
簡介
最短路問題是網路最優化中一個基本而又非常重要的問題，這一問題相對比較簡單，在實際生產和生活中經常遇到，許多的網路最優化問題可以化為最短路問題，或者用最短路演算法作為其子程序.因此，最短路的用途已遠遠超出其表面意義迄今為止，所有最短路演算法都只對不含負迴路的網路有效，實際上對含有負迴路的網路，其最短路問題是NP困難的，因此本研究所討論的網路也不含負迴路.此外，如果將無向圖每條邊用兩條端點相同、方向相反的弧來代替，可以將其化為有向圖，因而不討論無向圖.本研究中未述及的術語、記號。
Floyd演算法是一種用於尋找給定加權圖中頂點間最短路徑的演算法，以1978年圖靈獎獲得者斯坦福大學計算機科學系教授RobertW．Floyd命名。Floyd演算法採用帶升滲動態規劃的原理計算兩兩頂點間最短路徑，主要解決網路路由尋找最優路徑的問題。