85问答库 > 数据结构课程设计作业:求任意两点的最短路径问题,写个完整的程序..急求啊...小弟上学期没学好..解决加分谢

数据结构课程设计作业:求任意两点的最短路径问题,写个完整的程序..急求啊...小弟上学期没学好..解决加分谢

就是解决任意两点之间的最短路径…用Dijkstra算法实现…

2025-03-04 17:58:08

推荐回答（2个）

回答1：

一：
#include "stdafx.h"
#include
#include
#include
using namespace std;

const int MAXINT = numeric_limits::max();

template
void Dijkstra(int n, int v, Type dist[], int prev[], Type** c)
{

bool *s = new bool[n+1];
int i, j;
for(i = 1; i <=n; i++)
{
dist[i] = c[v][i];
if(c[v][i]!=MAXINT)
prev[i] = v;
else prev[i] =0;
s[i] = false;
}
s[v] = true;
dist[v] = 0;
prev[v] = 0;

for(i = 1; i< n; i++)
{

int u = v;
int temp = MAXINT;
for( j = 1; j<=n; j++)
if(!s[j]&&dist[j] {
u = j;
temp = dist[j];
}
s[u] = true;
for(j=1; j<=n; j++)
{
if((!s[j])&&c[u][j] {
if((dist[u]+c[u][j]) {
dist[j] = dist[u] + c[u][j];
prev[j] = u;
}
}
}

}

delete [] s;

}
void djpath(int m, int v, int prev[])
{
int i = m ,j =1;

while(i!=0)
{
if (j == 1)
{
cout<< i;
j = 0;
}
else
cout<< "-" << i;
i = prev[i];
}

cout<}

int _tmain(int argc, _TCHAR* argv[])
{
cout<<"最大整数:"< int prev[6], dist[6];
int i,j,n;
int** myc;

FILE *fp;
fp=fopen("data.txt", "r");
fscanf(fp,"%d", &n);

myc = new int* [n+1];
for(i =0; i<=n; i++)
myc[i] = new int[n+1];

for(i=1; i<=n; i++)
for(j =1; j<=n; j++)
{
fscanf(fp, "%d",&myc[i][j]);
if (myc[i][j]==-1)
myc[i][j] = MAXINT;
}

Dijkstra(5, 1, dist, prev, myc);

for(i = 1; i<=5; i++)
cout<
for(i=2; i<=5; i++)
djpath(i,1,prev);

for(i = 0; i<=5; i++)
delete[] myc[i];
delete [] myc;

return 0;
}

输入数据采用文本文件格式，下面是data.txt的内容:
5
0 10 -1 30 100
10 0 50 -1 -1
-1 50 0 20 10
30 -1 20 0 60
100 -1 10 60 0

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/mikewolf2009/archive/2009/09/12/4545537.aspx

二：
#include
using namespace std;

void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<
d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;ifor(i=0;ifor(j=0;jcin>>w[i][j];

for(s[0]=1,i=1;i{
s[i]=0;d[i]=w[0][i];
if(d[i] else p[i]=-1;
}

for(i=1;i{
t=infinity;k=1;
for(j=1;j if((!s[j])&&(d[j] s[k]=1;//point k join the S
for (j=1;j。且D[j]减小的新路径P只可能是由于路径和边组成。所以，当length(P)=D[k]+w小于D[j]时，应该用P的长度来修改D[j]的值。
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}

}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i}

以上二个代码都是完整可以使用的，楼主喜欢哪个就用那个吧。自己还是可以仔细分析下代码。

回答2：

就是两个坐标点算距离的吗？
是的话就简单了。

最新问答

大众迈腾烧机油怎么回事情？

华北水利水电学院三本有哪些专业

苹果手机wifi旁边总有个转圈圈的东西是什么意思

帕金森怎么治疗效果好?

脸上一了晒斑,谁有好办法?

漫长的反义词？

小孩在邵东读的幼儿园、夫妻都在邵东上班几年了、在邵东买了房、在有学位的情况下可以插班吗

骆驼祥子,钢铁是怎样炼成的,朝花夕拾的优美词句一共4000字很急！！！

为什么nba主场球队穿客场球衣，则客场穿主场球衣

Maya外包模型承接...