弗洛伊德算法常见问题

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是求任意两点之间的最短距离。要经过所有点的话可以用蚁群算法，模拟退火算法，遗传算法。