图的最短路径实现(数据结构课程设计)

《图的最短路径实现(数据结构课程设计)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内容和要求广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。进一步了解数据结构中对图的各种操作，以及求最短路径的算法。解决方案和关键代码解决方案：思路：首先把图用带权邻接矩阵g表示出来（每个城市看做一个顶点，广州是v0），然后用c语言实现书上的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v的最短路径保存到D[v]，以及途经的一个最近新的路径保存Path[v]。最后输出D[v]以及Path[

2、v]。其中：（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）关键代码#include#pragmawarning(disable:4996)usingnamespacestd;//定义我们需要的变量charcityName[7][256];//用于表示城市之间的关系,依次是广州,佛山,肇庆,珠海,深圳,南宁,香港intdis[7][7]={{-1,100,200,200,-1,-1,-1},{-1,-1,-1,50,150,-1,-1},{-1

3、,-1,-1,100,-1,150,-1},{-1,-1,-1,-1,80,350,-1},{-1,-1,-1,-1,-1,-1,150},{-1,-1,-1,-1,360,-1,450},{-1,-1,-1,-1,-1,-1,-1}};intfrom[7];intdisSum[7];intcurrent,current1;intnextNoList[7];intnextNoList1[7];charpath[7][256];chartemp[256];intmain(){//将广州等字符串复制给ci

4、tyName数组中strcpy(cityName[0],"广州");strcpy(cityName[1],"佛山");strcpy(cityName[2],"肇庆");strcpy(cityName[3],"珠海");strcpy(cityName[4],"深圳");strcpy(cityName[5],"南宁");strcpy(cityName[6],"香港");inti,j;for(i=0;i<7;i++){disSum[i]=-1;from[i]=-1;}current=1;nextNoList

5、[0]=0;disSum[0]=0;strcpy(path[0],cityName[0]);//用Dijkstra算法计算图的最短路径while(current){current1=0;for(j=0;j

6、

7、disSum[i]>disSum[nextNoList[j]]+dis[nextNoList[j]][i]){disSum[i]=disSum[

8、nextNoList[j]]+dis[nextNoList[j]][i];nextNoList1[current1++]=i;from[i]=nextNoList[j];strcpy(temp,path[nextNoList[j]]);strcat(temp,"->");strcat(temp,cityName[i]);strcpy(path[i],temp);}}}}current=current1;for(j=0;j

9、j];}}//显示各个效果for(i=1;i<7;i++){printf("从%s到%s:%d:%s",cityName[0],cityName[i],disSum[i],path[i]);}return0;}数据测试与结果总结：本次主要运用了Dijkstra算法（迪杰斯特拉算法）来求得两个点之间的最短路径，理论是还是很好明白的，但在本次的实验中，最难的就是上机实现这个算法问题。其他的还好，不过经过了数据结构的课程设计，让我明白了对于周围的人来说，我的算法很差，算法做了一个雏形之后，靠着舍友的调试

10、以及修改才完成了这个算法。