弗洛伊德演算法常見問題

1. floyd演算法的三重循環問題

三層循環的意思。第一層就是加入K的中間點，第二層和第三層循環是求每一對頂點在加入新的點後是否存在距離更近的路徑，所以K只能放在最外層。也就是說你再加入新的點後，再進行判斷每對頂點是否距離有變，就相當於一個前提條件。

2. VC++弗洛伊德演算法問題求教

int n=1改成2試試

3. 弗洛伊德演算法有向圖是否有漏洞

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

4. floyd演算法導游問題

因為你只記錄了u是否是k到j的最短路徑上的點。。。並沒有記錄他們的相對順序啊

試一下這個代碼可以不

voidPrintShortestPath(constMGraph*G,int(&p)[10][10][10],intst,inted){
	inti;
	for(i=0;i<G->vexnum;i++){
		if(i!=st&&i!=ed&&p[st][ed][i]){
			PrintShortestPath(G,p,st,i);
			PrintShortestPath(G,p,i,ed);
			return;
		}
	}
	printf("-->%s",G->vexs[ed].name);
}

voidFloyd(MGraph*G)
//用Floyd演算法求圖中各對頂點v和w之間的最短路徑P[v][w]及其
//帶權長度D[v][w]。若P[v][w][u]為1，則u是從v到w當前求得最短
//路徑上的頂點。
{
	intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];
	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]=0;
			if(D[v][w]<INFINITY)
			{
				p[v][w][v]=1;p[v][w][w]=1;
			}
		}
	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];
				}
	while(flag)
	{
		printf("請輸入出發點和目的地的編號:");
		scanf("%d%d",&k,&j);
		if(k<0||k>G->vexnum||j<0||j>G->vexnum)
		{
			printf("景點編號不存在!請重新輸入出發點和目的地的編號:");
			scanf("%d%d",&k,&j);
		}
		if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)
			flag=0;
	}
	printf("%s",G->vexs[k].name);
	PrintShortestPath(G,p,k,j);
	printf("總路線長%dm
",D[k][j]);

}//Floydend

5. 數據結構 圖 最短路徑問題 迪傑斯特拉演算法和弗洛伊德演算法問題

1. dijkstra 不能有負權邊，否則結果是錯的，你想想，假如無向圖有1,2,3個點，w(1,2)=1,w(1,3)=2,w(2,3)=-2. 按dij演算法求求看。
2.這句話還沒找到反例...不過教floyd時說是用在非負權邊上的，除了負的迴路之外應該還有漏洞吧..

6. 跪求 弗洛伊德演算法 一個錯誤的解釋：

floyd演算法用以解決所有點對最短路徑。

floyd演算法基本思想是遞推，動態規劃。我們記 dp[j][k] 表示圖中頂點 i 到 j 的最短路徑，且該最短路徑中，所經過的中間頂點(不包括 i, j) 的范圍為 [1,k]，由此我們可以得到以下遞推式：

dp[j][k]= w[j] 如果 k== 0

dp[j][k]= min{ dp[k][k-1]+ dp[k][j][k-1] } 如果 k>= 1。

實際中，空間上我們可以減少一維。

floyd演算法同樣可以來解決一些其它問題

1) 有向圖的最小(或最大)環

這個問題答案其實就是自身到自身的最短路徑，運行完 floyd 後，對每個頂點取自身到自身距離的最小者。

2) 無向圖的最小環

根據以上的遞推式，dp[j][k] 表示 i 到 j 的最短路徑，且該最短路徑中，所經過的中間頂點(不包括 i, j) 的范圍為 [1,k]。

此時我們可以枚舉出頂點序列最大為 k+ 1 的所有最小環，如何枚舉：設與頂點序列最大的頂點 k+ 1 相連的兩個頂點為 x, y，x,y 須滿足 x, y<= k。這樣最小環構成為 邊<x,k+1> 邊<k+ 1, y> 及 x 到 y 的最短路徑。

Poj 1734 Sightseeing trip

#include <stdio.h>
#include <stdlib.h>

int const N= 110, inf= 5000000;
int mat[N][N], dist[N][N], pre[N][N], path[N], n, m, top= 0, p;

#define min(a,b) ((a)<(b)?(a):(b))

int main(){
scanf("%d%d",&n,&m );
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j ){
mat[j]= inf; dist[j]= inf; pre[j]= j; }
while( m-- ){
int u, v, d;
scanf("%d%d%d",&u,&v,&d);
mat[v]= min( mat[v], d );
mat[v]= mat[v];
dist[v]= mat[v]; dist[v]= mat[v];
}
int ans= inf;
for( int k= 1; k<= n; ++k ){
for( int x= 1; x< k; ++x )
for( int y= 1; y< x; ++y ){
if( mat[x][k]+ mat[k][y]+ dist[x][y]< ans ){
ans= mat[x][k]+ mat[k][y]+ dist[x][y];
top= 0; path[top++]= k; p= x;
while( p!= y ){
path[top++]= p; p= pre[p][y];
}
path[top++]= y;
}
}
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
if( dist[k]+ dist[k][j]< dist[j] ){
dist[j]= dist[k]+ dist[k][j];
pre[j]= pre[k]; }
}
if( top> 0 ){
printf("%d", path[0] );
for( int i= 1; i< top; ++i ) printf(" %d", path );
puts("");
}else puts("No solution.");

return 0;
}

7. Floyd演算法的優缺點分析

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

8. 最短路的Floyd演算法有些不明白的地方，請求大神支援

floyd演算法本質是動態規劃，可以寫成三維來理解
f[k][i][j]表示如果除去起點和終點路徑上只包含編號為1到k的點的話，從i號點走到j號點的最短路是f[k][i][j]

那麼我們依次的擴大k，當k從1擴大到n，最終的答案也就得出

考慮如何從從k推到k+1。首先，最短路不可能經過k+1號點兩次，所以一條包含k+1號點的最短路必然是由一段只包含1~k的點的路徑P1+(k+1號點)+另一端只包含1~k的點的路徑P2得出的，枚舉起點i和終點j，拼接得的長度為f[k][i][k+1]+f[k][k+1][j]

仔細觀察後又會發現，將第一維拿掉絲毫不影響答案，將第一維刪除後，就得到了用兩維數組存儲的floyd演算法。

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

10. 弗洛伊德演算法能不能經過圖上所有點如果要求經過圖上所有點的最短路徑,應該用什麼方法

floyd是求任意兩點之間的最短距離。要經過所有點的話可以用蟻群演算法，模擬退火演算法，遺傳演算法。