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

内容和要求广东省主要大城市之间的交通图如下所示，每条边上的权值代表从城市A到城市B的路途长度，使用数据结构图的相关理论编程给出广州到各个城市的最短路径，并且输出经过的路径。 进一步了解数据结构中对图的各种操作，以及求最短路径的算法。解决方案和关键代码解决方案：思路：首先把图用带权邻接矩阵g表示出来（每个城市看做一个顶点，广州是v0），然后用c语言实现书上的迪杰斯特拉算法，求有向网g的v0顶点到其余顶点v的最短路径保存到Dv，以及途经的一个最近新的路径保存Pathv。最后输出Dv以及Pathv。其中：（v0是广州；v1是佛山；v2是肇庆；v3是珠海；v4是深圳；v5是南宁；v6是香港）关键代码#include #pragma warning (disable:4996)using namespace std;/定义我们需要的变量char cityName7256;/用于表示城市之间的关系,依次是广州,佛山,肇庆,珠海,深圳,南宁,香港int dis77 = -1, 100, 200, 200, -1, -1, -1 , -1, -1, -1, 50, 150, -1, -1 , -1, -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 ;int from7;int disSum7;int current, current1;int nextNoList7;int nextNoList17;char path7256;char temp256; int main() /将广州等字符串复制给cityName数组中 strcpy(cityName0, 广州); strcpy(cityName1, 佛山); strcpy(cityName2, 肇庆); strcpy(cityName3, 珠海); strcpy(cityName4, 深圳); strcpy(cityName5, 南宁); strcpy(cityName6, 香港); int i, j; for (i = 0; i 7; i+) disSumi = -1; fromi = -1; current = 1; nextNoList0 = 0; disSum0 = 0; strcpy(path0, cityName0); /用Dijkstra算法计算图的最短路径 while (current) current1 = 0; for (j = 0; j current; j+) for (i = 1; i disSumnextNoListj + disnextNoListji) disSumi = disSumnextNoListj + disnextNoListji; nextNoList1current1+ = i; fromi = nextNoListj; strcpy(temp, pathnextNoListj); strcat(temp, - ); strcat(temp, cityNamei); strcpy(pathi, temp); current = current1; for (j = 0; j current1; j+) nextNoListj = nextNoList1j; /显示各个效果 for (i = 1; i 7; i+) printf(从%s到%s : %d : %sn, cityName0, cityNamei, disSumi, pathi); return 0;数据测试与结果总结：本次主要运用了Dijkstra算法（迪杰斯特拉算法）来求得两个点之间的最短路径，理论是还是很好明白的，但在本次的实验中，最难的