Question

一个c语言编程球最短路问题....

假设有一个n个点的图，现在我一直其中的m个点（m<n）。
现在我想在这m个顶点里求一条最短路，应该如何实现？
求代码....
解决了加送分！！！！

Answer 1

用floyd算法（时间复杂度为0(N*3)）
具体实现如下：
#include<fstream>
#define Maxm 501
using namespace std;
ifstream fin;
ofstream fout("APSP.out");
int p,q,k,m;
int Vertex,Line[Maxm];
int Path[Maxm][Maxm],Map[Maxm][Maxm],Dist[Maxm][Maxm];
void Root(int p,int q)
{
if (Path[p][q]>0)
{
Root(p,Path[p][q]);
Root(Path[p][q],q);
}
else
{
Line[k]=q;
k++;
}
}
int main()
{
memset(Path,0,sizeof(Path));
memset(Map,0,sizeof(Map));
memset(Dist,0,sizeof(Dist));
fin >> Vertex;
for(p=1;p<=Vertex;p++)
for(q=1;q<=Vertex;q++)
{
fin >> Map[p][q];
Dist[p][q]=Map[p][q];
}
for(k=1;k<=Vertex;k++)
for(p=1;p<=Vertex;p++)
if (Dist[p][k]>0)
for(q=1;q<=Vertex;q++)
if (Dist[k][q]>0)
{
if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q))
{
Dist[p][q]=Dist[p][k]+Dist[k][q];
Path[p][q]=k;
}
}
for(p=1;p<=Vertex;p++)
{
for(q=p+1;q<=Vertex;q++)
{
fout << "\n==========================\n";
fout << "Source:" << p << '\n' << "Target " << q << '\n';
fout << "Distance:" << Dist[p][q] << '\n';
fout << "Path:" << p;
k=2;
Root(p,q);
for(m=2;m<=k-1;m++)
fout << "-->" << Line[m];
fout << '\n';
fout << "==========================\n";
}
}
fin.close();
fout.close();
return 0;
}

Answer 2

[code=C/C++][/code]#include"stdio.h"
#include"string.h"
#define Lm 20000
int main()
{
int map[102][102],i,j,k,m,n,a,b;
while(scanf("%d%d",&n,&m)&&(m||n)){
memset(map,0,sizeof(map));
while(m--) {scanf("%d%d",&a,&b);scanf("%d",&map[a][b]);map[b][a]=map[a][b];}
for(i=0;i<102;i++)
for(j=0;j<102;j++) if(map[i][j]==0) map[i][j]=Lm;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
if(i==j||i==k||k==j) continue;
if(map[i][k]<Lm&&map[k][j]<Lm&&map[i][j]-map[i][k]>map[k][j])
{map[i][j]=map[i][k]+map[k][j];}
}
printf("%d\n",map[1][n]);
}
}

Answer 3

floyed算法,你这个比较麻烦 ,然后你再两次for循环比较求最大值，就解决了，还可以直接用dijistra