有一个题我不知道该怎么答,是道考题,能帮我解答吗?
题目是:写出任意两点之间最短路径的递归算法,并说明为什么改算法可以实现该功能。
我用的殷人昆的《数据结构c++版》上面只有用数组实现的算法,递归算法应该怎么写呢?
写了一个,你看看,不保证是对的,
递归的效率还是比较差的,还是迭代好,几行就搞定了
输入 :图的邻接矩阵,无边距离为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]