| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1082 人关注过本帖
标题:求任意两点最短路经得递归算法怎么写???
只看楼主 加入收藏
lemon_wb
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-9-19
收藏
 问题点数:0 回复次数:2 
求任意两点最短路经得递归算法怎么写???

有一个题我不知道该怎么答,是道考题,能帮我解答吗?
题目是:写出任意两点之间最短路径的递归算法,并说明为什么改算法可以实现该功能。
我用的殷人昆的《数据结构c++版》上面只有用数组实现的算法,递归算法应该怎么写呢?

搜索更多相关主题的帖子: 递归算法 路经 数据结构 殷人昆 考题 
2006-09-19 11:19
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 

写了一个,你看看,不保证是对的,
递归的效率还是比较差的,还是迭代好,几行就搞定了

输入 :图的邻接矩阵,无边距离为0;
输出 : 无边距离为max.
[CODE]#include<stdio.h>
#include<string.h>
int min(int a,int b)
{
return a<b?a:b;
}
#define M 50
#define max 10000000
int dist[M][M][M];
int a[M][M];
int mindist(int i,int j,int k)
{
if(dist[i][j][k]!=max)return dist[i][j][k];
if(k==0)return a[i][j];
else
{
dist[i][j][k]=min(mindist(i,j,k-1),mindist(i,k,k-1)+mindist(k,j,k-1));
}
return dist[i][j][k];
}
int main()
{
int n;
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
dist[i][j][k]=max;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0)a[i][j]=max;
dist[i][j][0]=a[i][j];
}
a[i][i]=0;
dist[i][i][0]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
mindist(i,j,n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",dist[i][j][n]);
printf("\n");
}

}[/CODE]


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-09-19 12:26
lemon_wb
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-9-19
收藏
得分:0 
太好了

书上写的很抽象,看到程序就明白了,太感谢了~~~~~!!!!!!

[此贴子已经被作者于2006-9-19 15:50:25编辑过]

2006-09-19 14:53
快速回复:求任意两点最短路经得递归算法怎么写???
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028546 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved