要求:要能输出图形的最短路径设计,用C语言编写,高手进!!!

来源:百度知道 编辑:UC知道 时间:2024/06/16 01:27:49
题目:路径设计问题
要求:已知若干个城市的地图,如图所示,求从沈阳到广州的路径,要求路径中经过的城市最少,画出如图所示的路径网络图,然后动态显示所选择的路径。

这个是我以前参加省赛的时候写的,一直保存着的,应该是你这个问题的答案,语法上没有问题,因为以前我跑过的,这个是C++程序,不过C和C++在基础语法上没有任何区别的,在这里拿出来跟你分享,希望能得到你的分哦!呵呵!

/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异的顶点s称为缘。
单源最短路径问题,或者称为最短路径问题,是要确定从s到V中没一个其他
顶点的距离,这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给了c++下的源代码!
************************************************/
#include<iostream.h>
void main()
{
int infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";
cin>>n;
cout<<endl;

d=new int[n];
s=new int[n];
p=new int[n];
w=new int*[n];
for(i=0;i<n;i++) {w[i]=new int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];

for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity) p[i]=0;
else p[i]=-1;
}

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