Question

计算给定的有向图邻接的矩阵中的每对顶点之间的最短路径 要求详细 在c语言或c++ 的环境中 还有代码 谢谢

回答的好有追加

Answer 1

//Floyed 实现赋权无向图定点对间的最短路径，时间复杂度O(n^3)
1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。 　　
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
#include<stdio.h>
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("输入图的顶点数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("输入边(%d,%d)的权值,若不存在输入10000:",i,j);
scanf("%d",&c[i][j]);
}
}
如果是有向图就删掉这里"//for(i=1;i<=n;i++)
//{
///////////////////////////////////////for(j=1;j<=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i<=n;i++)
c[i][i]=0;//自己到自己的权值为0
for(i=1;i<=n;i++) //初始化路径
{
for(j=1;j<=n;j++)
parth[i][j]=0;
}
for(k=1;k<=n;k++)//k是中间节点，i是起点j是中点。其实就是枚举中间节点，来求i j 的最短路径
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000&&t2!=10000&&(t3==10000||t1+t2<t3)) //松弛 覆盖原来的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//记录i j的中间点是k
}
}
}
while(1)//也可以用递归的形式输出parth
{
printf("输入2点:");
scanf("%d%d",&x,&y);
printf("最短距离为%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}

除了使用floyed算法也可以做n次digstra时间复杂度也是N立方 就是在dijstra的基础上
加一个for循环
详情请百度floyed算法 或dijstra算法
比较难理解 多画画图就理解了 手工机械模拟一下 理解了就绝的挺简单的了

追问

那个我觉得回答的有点不对

追答

?哪里不对了

追问

那个大神 有流程图 追加30 呵呵

追答

我这儿只有dijstra算法的flash动画 没有floyed的 我觉得如果理解了dijstra的话就很容易理解floyed
floyed还是很好理解的 无非就是枚举中间点
你要dijstra的动画的话 请留下邮箱 我明天就去上学可能不能及时发送

追问

哦 809310501@qq.com 谢了 我们作业 是这个