floyd演算法p表

『壹』 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]這條路

『貳』 p->weight如何對二維數組附值D[i][j]=p->weight這樣是錯誤的

這是一個關於FLOYD演算法的應用，對於大多數數據結構書上和網上資料中來說，他們都是在用鄰接矩陣來解決FLOYD演算法，可是我希望用鄰接表來處理這個問題，鄰接表佔用的空間小，但是編寫程序相對復雜一些，希望高手積極回答~鄰接表我已經建立好了，就是在附值上出現了問題，非常郁悶~苦思冥想也沒想出正確路子~很悲劇~急急急呀!!!!
問題補充：void Floyd(int n,int Q[][maxint],int D[][maxint])//Q為路徑D為權值
{
int i,j,k;
arctype *p,*q;
adjlisttype graph;
for(i=1;i<=n;i++)//設置路徑長度和路徑初值
for(j=1,p=graph[j].firstarc;j<=n,p!=NULL;j++,p=p->nextarc)
{ if(p->weight!=maxint)//<---這里的問題
Q[i][j]=j;//j是i的後繼
else
Q[i][j]=0;
D[i][j]=p->weight;//<---這里的問題
}
for(k=1;k<=n;k++)
{//做K次迭代，每次均試圖將頂點擴充到當前求得的i到j的最短路徑上
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(D[i][k]+D[k][j]<D[i][j])
{

『叄』 弗洛伊德的演算法（Floyd』s algorithm ）

假設這個圖的weight matrix存在map[5][5]中，

for(intk=0;k<5;k++)
for(inti=0;i<5;i++)
for(intj=0;j<5;j++)if(i!=j){
if(map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}

處理完之後map[i][j]存的就是i，j之間的最短路徑長度。

簡單的說，當執行完一次最外層循環時，map記錄的時i，j之間允許使用中間節點｛0, ..., k｝的最短路徑。

『肆』 Floyd演算法的參考代碼

function Floyd(w,router_direction,MAX)
%w為此圖的距離矩陣
%router_direction為路由類型：0為前向路由；非0為回溯路由
%MAX是數據輸入時的∞的實際值
len=length(w);
flag=zeros(1,len);
%根據路由類型初始化路由表
R=zeros(len,len);
for i=1:len
if router_direction==0%前向路由
R(:,i)=ones(len,1)*i;
else %回溯路由
R(i,:)=ones(len,1)*i;
end
R(i,i)=0;
end
disp('');
disp('w(0)');
dispit(w,0);
disp('R(0)');
dispit(R,1);
%處理端點有權的問題
for i=1:len
tmp=w(i,i)/2;
if tmp~=0
w(i,:)=w(i,:)+tmp;
w(:,i)=w(:,i)+tmp;
flag(i)=1;
w(i,i)=0;
end
end
%Floyd演算法具體實現過程
for i=1:len
for j=1:len
if j==i || w(j,i)==MAX
continue;
end
for k=1:len
if k==i || w(j,i)==MAX
continue;
end
if w(j,i)+w(i,k)<w(j,k) %Floyd演算法核心代碼
w(j,k)=w(j,i)+w(i,k);
if router_direction==0%前向路由
R(j,k)=R(j,i);
else %回溯路由
R(j,k)=R(i,k);
end
end
end
end
%顯示每次的計算結果
disp(['w(',num2str(i),')'])
dispit(w,0);
disp(['R(',num2str(i),')'])
dispit(R,1);
end
%中心和中點的確定
[Center,index]=min(max(w'));
disp(['中心是V',num2str(index)]);
[Middle,index]=min(sum(w'));
disp(['中點是V',num2str(index)]);
end
function dispit(x,flag)
%x：需要顯示的矩陣
%flag：為0時表示顯示w矩陣，非0時表示顯示R矩陣
len=length(x);
s=[];
for j=1:len
if flag==0
s=[s sprintf('%5.2f ',x(j,:))];
else
s=[s sprintf('%d ',x(j,:))];
end
s=[s sprintf(' ')];
end
disp(s);
disp('---------------------------------------------------');
end
% 選擇後按Ctrl+t取消注釋號%
%
% 示例：
% a=[
% 0,100,100,1.2,9.2,100,0.5;
% 100,0,100,5,100,3.1,2;
% 100,100,0,100,100,4,1.5;
% 1.2,5,100,0,6.7,100,100;
% 9.2,100,100,6.7,0,15.6,100;
% 100,3.1,4,100,15.6,0,100;
% 0.5,2,1.5,100,100,100,0
% ];
%
% b=[
% 0,9.2,1.1,3.5,100,100;
% 1.3,0,4.7,100,7.2,100;
% 2.5,100,0,100,1.8,100;
% 100,100,5.3,0,2.4,7.5;
% 100,6.4,2.2,8.9,0,5.1;
% 7.7,100,2.7,100,2.1,0
% ];
%
% Floyd(a,1,100)
% Floyd(b,1,100) program floyd;
var
st,en,f:integer;
k,n,i,j,x:integer;
a:array[1..10,1..10] of integer;
path:array[1..10,1..10] of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(k);
if k<>0 then
a[i,j]:=k
else
a[i,j]:=maxint;
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
f:=st;
while f<> en do
begin
write(f);
write('-->');
f:=path[f,en];
end;
writeln(en);
end. //以無向圖G為入口，得出任意兩點之間的路徑長度length[i][j]，路徑path[i][j][k]，//途中無連接得點距離用0表示，點自身也用0表示publicclassFLOYD{int[][]length=null;//任意兩點之間路徑長度int[][][]path=null;//任意兩點之間的路徑publicFLOYD(int[][]G){intMAX=100;introw=G.length;//圖G的行數int[][]spot=newint[row][row];//定義任意兩點之間經過的點int[]onePath=newint[row];//記錄一條路徑length=newint[row][row];path=newint[row][row][];for(inti=0;i<row;i++)//處理圖兩點之間的路徑for(intj=0;j<row;j++){if(G[i][j]==0)G[i][j]=MAX;//沒有路徑的兩個點之間的路徑為默認最大if(i==j)G[i][j]=0;//本身的路徑長度為0}for(inti=0;i<row;i++)//初始化為任意兩點之間沒有路徑for(intj=0;j<row;j++)spot[i][j]=-1;for(inti=0;i<row;i++)//假設任意兩點之間的沒有路徑onePath[i]=-1;for(intv=0;v<row;++v)for(intw=0;w<row;++w)length[v][w]=G[v][w];for(intu=0;u<row;++u)for(intv=0;v<row;++v)for(intw=0;w<row;++w)if(length[v][w]>length[v][u]+length[u][w]){length[v][w]=length[v][u]+length[u][w];//如果存在更短路徑則取更短路徑spot[v][w]=u;//把經過的點加入}for(inti=0;i<row;i++){//求出所有的路徑int[]point=newint[1];for(intj=0;j<row;j++){point[0]=0;onePath[point[0]++]=i;outputPath(spot,i,j,onePath,point);path[i][j]=newint[point[0]];for(ints=0;s<point[0];s++)path[i][j][s]=onePath[s];}}}voidoutputPath(int[][]spot,inti,intj,int[]onePath,int[]point){//輸出i//到j//的路徑的實際代碼，point[]記錄一條路徑的長度if(i==j)return;if(spot[i][j]==-1)onePath[point[0]++]=j;//System.out.print(+j+);else{outputPath(spot,i,spot[i][j],onePath,point);outputPath(spot,spot[i][j],j,onePath,point);}}publicstaticvoidmain(String[]args){intdata[][]={{0,27,44,17,11,27,42,0,0,0,20,25,21,21,18,27,0},//x1{27,0,31,27,49,0,0,0,0,0,0,0,52,21,41,0,0},//1{44,31,0,19,0,27,32,0,0,0,47,0,0,0,32,0,0},//2{17,27,19,0,14,0,0,0,0,0,30,0,0,0,31,0,0},//3{11,49,0,14,0,13,20,0,0,28,15,0,0,0,15,25,30},//4{27,0,27,0,13,0,9,21,0,26,26,0,0,0,28,29,0},//5{42,0,32,0,20,9,0,13,0,32,0,0,0,0,0,33,0},//6{0,0,0,0,0,21,13,0,19,0,0,0,0,0,0,0,0},//7{0,0,0,0,0,0,0,19,0,11,20,0,0,0,0,33,21},//8{0,0,0,0,28,26,32,0,11,0,10,20,0,0,29,14,13},//9{20,0,47,30,15,26,0,0,20,10,0,18,0,0,14,9,20},//10{25,0,0,0,0,0,0,0,0,20,18,0,23,0,0,14,0},//11{21,52,0,0,0,0,0,0,0,0,0,23,0,27,22,0,0},//12{21,21,0,0,0,0,0,0,0,0,0,0,27,0,0,0,0},//13{18,41,32,31,15,28,0,0,0,29,14,0,22,0,0,11,0},//14{27,0,0,0,25,29,33,0,33,14,9,14,0,0,11,0,9},//15{0,0,0,0,30,0,0,0,21,13,20,0,0,0,0,9,0}//16};for(inti=0;i<data.length;i++)for(intj=i;j<data.length;j++)if(data[i][j]!=data[j][i])return;FLOYDtest=newFLOYD(data);for(inti=0;i<data.length;i++)for(intj=i;j<data[i].length;j++){System.out.println();System.out.print(From+i+to+j+pathis:);for(intk=0;k<test.path[i][j].length;k++)System.out.print(test.path[i][j][k]+);System.out.println();System.out.println(From+i+to+j+length:+test.length[i][j]);}}}

『伍』 Floyd演算法，求高手幫忙修改，能計算小數。輸入的權矩陣要能包括小數，現在只能輸入整數，跪求！

把第2個和第2個以後的%d改成%f,估計就成了，前面你定義了連個浮點型的二維數組，輸入的時候用%d,輸入小數後會改成整形的。

『陸』 Floyd演算法的優缺點分析

Floyd演算法適用於APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動態規劃演算法，稠密圖效果最佳，邊權可正可負。此演算法簡單有效，由於三重循環結構緊湊，對於稠密圖，效率要高於執行|V|次Dijkstra演算法，也要高於執行V次SPFA演算法。
優點：容易理解，可以算出任意兩個節點之間的最短距離，代碼編寫簡單。
缺點：時間復雜度比較高，不適合計算大量數據。

『柒』 matlab floyd 演算法注釋

A矩陣是鄰接矩陣，對角線上為o，其餘位置數字表示的是兩點之間距離，比如A(1,2)=2,表示從第一個點到第二個點的距離為2.inf是無窮大的意思，這里表示沒有直接溝通這兩點的路。
n=length(D);設定n為D矩陣的長度。
接下來的兩重循環，得到的R矩陣是n*n的矩陣，它每個數據表示的是路徑，比如：R(1,3)=1;表示路徑為：1-1-3.這里是初始化路徑了。
後面的三重循環是floyd演算法的關鍵所在，就是更新路線了。裡面的那個判斷指的是：
假設有3個點，1
2
3；如果我從1-2-3之間總距離小於1-3的距離，那麼我R(1,3)=2；這就是選取更近的路線了。
最後的兩個判斷是為了不讓曾經走過的點再次被遍歷。就是不回頭的意思了，這個一般都可以忽略了，你照打上去就是了。
不知道這樣的解釋你是否滿意。

『捌』 floyd-warshall演算法的演算法概述

單獨一條邊的路徑也不一定是最佳路徑。 從任意一條單邊路徑開始。所有兩點之間的距離是邊的權的和，(如果兩點之間沒有邊相連, 則為無窮大）。 對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 不可思議的是，只要按排適當，就能得到結果。// dist(i,j) 為從節點i到節點j的最短距離
For i←1to n do
For j←1to n do
dist(i,j) = weight(i,j)
For k←1to n do// k為「媒介節點」{一定要先枚舉媒介節點}
For i←1to n do
For j←1to n do
if(dist(i,k) + dist(k,j) < dist(i,j))then// 是否是更短的路徑？
dist(i,j) = dist(i,k) + dist(k,j)
這個演算法的效率是O(V^3)。它需要鄰接矩陣來儲存圖。
這個演算法很容易實現，只要幾行。
即使問題是求單源最短路徑，還是推薦使用這個演算法，如果時間和空間允許(只要有放的下鄰接矩陣的空間，時間上就沒問題)。
計算每一對頂點間的最短路徑（floyd演算法）

『玖』 用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");
}
}

『拾』 Floyd演算法的演算法過程

1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，如果兩點之間沒有邊相連，則權為無窮大。
2，對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。
把圖用鄰接矩陣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直接相連。