弗洛伊德演算法最短路徑

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

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

B. 用弗洛伊德演算法求最短路徑

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

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

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

D. 用Floyd演算法求有向網G中各對頂點之間的最短路徑

#define MAX_NAME 5 // 頂點字元串的最大長度+1
#define MAX_INFO 20 // 相關信息字元串的最大長度+1
typedef int VRType;
typedef char VertexType[MAX_NAME];
typedef char InfoType;
#include"c1.h"
#include"c7-1.h"
#include"bo7-1.cpp"
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; void ShortestPath_FLOYD(MGraph G,PathMatrix &P,DistancMatrix &D)
{ // 用Floyd演算法求有向網G中各對頂點v和w之間的最短路徑P[v][w]及其
// 帶權長度D[v][w]。若P[v][w][u]為TRUE,則u是從v到w當前求得最短
// 路徑上的頂點。
int u,v,w,i;
for(v=0;v<G.vexnum;v++) // 各對結點之間初始已知路徑及距離
for(w=0;w<G.vexnum;w++)
{
D[v][w]=G.arcs[v][w].adj;
for(u=0;u<G.vexnum;u++)
P[v][w][u]=FALSE;
if(D[v][w]<INFINITY) // 從v到w有直接路徑
{
P[v][w][v]=TRUE;
P[v][w][w]=TRUE;
}
}
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]) // 從v經u到w的一條路徑更短
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
} void main()
{
MGraph g;
int i,j,k,l,m,n;
PathMatrix p;
DistancMatrix d;
CreateDN(g);
for(i=0;i<g.vexnum;i++)
g.arcs[i][i].adj=0; // ShortestPath_FLOYD()要求對角元素值為0
printf("鄰接矩陣:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%11d",g.arcs[i][j]);
printf("\n");
}
ShortestPath_FLOYD(g,p,d);
printf("d矩陣:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%6d",d[i][j]);
printf("\n");
}
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
printf("%s到%s的最短距離為%d\n",g.vexs[i],g.vexs[j],d[i][j]);
printf("p矩陣:\n");
l=strlen(g.vexs[0]); // 頂點向量字元串的長度
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(i!=j)
{
m=0; // 佔位空格
for(k=0;k<g.vexnum;k++)
if(p[i][j][k]==1)
printf("%s",g.vexs[k]);
else
m++;
for(n=0;n<m*l;n++) // 輸出佔位空格
printf(" ");
}
else
for(k=0;k<g.vexnum*l;k++) // 輸出佔位空格
printf(" ");
printf(" "); // 輸出矩陣元素之間的間距
}
printf("\n");
}
}

E. floyd演算法求最短路徑

Floyd演算法適用於APSP(AllPairsShortestPaths)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法。

優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單

缺點：時間復雜度比較高，不適合計算大量數據。

時間復雜度:O(n^3)；空間復雜度:O(n^2)；

任意節點i到j的最短路徑兩種可能：

直接從i到j；
從i經過若干個節點k到j。
map（i，j）表示節點i到j最短路徑的距離，對於每一個節點k，檢查map（i，k）+map（k，j）小於map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍歷每個k，每次更新的是除第k行和第k列的數。

步驟：

第1步：初始化map矩陣。
矩陣中map[i][j]的距離為頂點i到頂點j的權值；

如果i和j不相鄰，則map[i][j]=∞。

如果i==j，則map[i][j]=0;
第2步：以頂點A(假設是第1個頂點)為中介點，若a[i][j] > a[i][1]+a[1][j]，則設置a[i][j]=a[i][1]+a[1][j]。

F. 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]這條路

G. floyd演算法中輸出最短路徑序列的C語言代碼

void path(int i,int j)
{
int k;
if(P[i][j][i]==FALSE)
printf("There's no path!");
return;
for(k=0;k<n;k++)
if(P[i][j][k]==TRUE)
{
path(i,k);
path(k,j);
break;
}
}
void print(){
int v,w,u,i;
for (v=0;v<n;++v)
{
for (w=0;w<n;++w)
printf(" %d ",D[v][w]);
printf("\n");
}
printf("Please input the tailvex v1 and headvex v2:");
scanf("v1=%d,v2=%d",&v,&w);
path(v,w);
}
以上兩段應該對你有用。

H. 【討論】最短路徑弗洛伊德演算法的時間復雜度

那麼你的意思是說四個循環全部都執行了的哦？否則就不是O(n4)。你看最後一個循環是需要判斷進入的，也就是說，那個循環在最內層，本身次數就少，加上排除不合法條件，很少能執行到，根據演算法思想，那麼應該忽略常數級

I. 弗洛伊德演算法如何去記錄最短路徑經過的每一個結點

用path數組的遞歸實現列印

例如：列印i,j之間的路徑

當path[i][j]的值為k時，分別再去列印i,k和k,j之間的路徑

如此遞歸直至兩點間直接有邊相連