实验六最短路径
一、实验目的
1.学习掌握图的存储结构
2.学会编写求最短路径的算法
二、实验内容
1、实验题目
编写代码实现Dijkstra生成最短路径的算法，其中要有完整的图的输入输出
2、简单介绍
图的存储：用邻接矩阵，这样会方便不少。
邻接矩阵是一个二维数组，数组中的元素是边的权(一些数值)，数组下标号为结点的标号。(1)例如二维数组中的一个元素M[5][6]的值为39，则表示结点5、6连接，且其上的权值为39。
(2)用邻接矩阵存储图，对图的读写就简单了。因为邻接矩阵就是一个二维数组，因此对图的读写就是对二维数组的操作。只要能弄清楚边的编号，就能把图读入了。
用一对结点表示边(也就是输入的时候输入一对结点的编号)
求最短路径的算法：
求最短路径就是求图中的每一个点到图中某一个给定点(这里认为是编号为0的点)的最短距离。
具体算法就是初始有一个旧图，一个新图。开始的时候旧图中有所有的结点，新图中初始为只有一个结点(源点，路径的源头)。整个算法就是不停的从旧图中往新图中添加点，直到所有的点都添加到新图中为止。
要实现这个算法，除了用二维数组保存图，还需要使用到两个辅助的数组
数组find[N]：此数组是用来表示标号对应的结点是否已经被添加到新图中(因为只有旧图中的点我们才需要添加到新图中，并且只有旧图中点到源点的距离，我们才需要进行更新)其中N为图中结点的个数。
数组distance[N]：此数组记录图中的点到源点的距离。这个数组里面存放的值是不断进行更新的。其中N为图中结点的个数。

一、最短路径
最短路径：从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径。
求最短路径的四个算法如下：
二、算法概述
【Dijkstra算法】
单源最短路：从单个源点出发，到所有结点的最短路
作用：计算正权图上的单源最短路。
图类型：有向图、无向图。
限制：边权为正。
【Bellman-Ford算法】
事实1：当负权存在时，连最短路都不一定存在。
事实2：如果最短路存在，一定存在一个不含环的最短路。
作用：计算图上的单源最短路(前提是最短路存在)。
图类型：有向图、无向图。
优势：边权可为负。
【Floyd算法】
作用：求出每两点之间的最短路。
图类型：有向图、无向图。
特点：如果要用Dijkstra或Bellman-ford求出每两点之间的最短路，那么需要调用n次Dijkstra(边权均为正)或者Bellman-ford(有负权)。
三、负权问题
如果一个图仅仅是存在负权，但不构成负权回路，又该如何？
Dijkstra 算法
观察上图，若 A 作为源点，在第一轮循环后，B 被标记数组标记，但我们发现在第二轮循环中，B 还可以通过 C 点继续进行更新。由此，可以得出结论：Dijkstra 算法不适用于负权图。
Bellman_Ford 算法和 SPFA 算法
我们先思考下上述 “因 B 点被标记数组标记而导致无法通过 C 点再更新” 的问题，归根结底是标记数组的锅。有人提议，不妨去掉标记数组，如果去掉，就会造成很严重的问题，首当其冲的是“无法求出dist[]的最小值”。
反观 Bellman_Ford 算法和 SPFA 算法，它们不存在标记数组的问题，因此对于仅仅存在负权的图，它们都可以工作的很好。
最后，读者需要注意的是，如果是无向图，只要存在一条负边，该图就存在负权回路，这不难理解，无向图的一条边相当于有向图的往返两条边。
四、补充分析
Dijkstra，Bellman_Ford 和 SPFA，该用哪个？
Bellman_Ford 没什么好说的，能不用就不用。
国际上一般不承认 SPFA 算法，因为在 SPFA 算法论文中对它的复杂度证明存在错误，其次 Bellman_Ford 的论文中已提及过这个队列优化。
SPFA 算法有两个优化策略 SLF 和 LLL。
SLF，Small Label First 策略，设要加入的节点是 j，队首元素为 i，若dist[j] < dist[i]，则将 j 插入队首，否则插入队尾；
LLL，Large Label Last 策略，设队首元素为 i，队列中所有 dist 值的平均值为 x，若dist[i] > x则将 i 插入到队尾，查找下一元素，直到找到某一 i 使得dist[i] <= x，则将 i 出队进行松弛操作。
SLF 可使速度提高 15 ~ 20%，SLF + LLL 可提高约 50%。 在实际的应用中 SPFA 的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法。
使用邻接表 + 二叉堆优化的 Dijkstra 算法，复杂度适宜，也稳定，就是有个缺陷，不能处理负权回路。
最后话个唠，我发现在算法竞赛中我们大多数的选择还是 SPFA，知乎了下，邻接表 + 二叉堆优化的 Dijkstra 写起来复杂，容易错，而 SPFA 代码简单，容易写，但是会被题目卡数据。
总结：首选 Dijkstra，其次 SPFA，最后 Bellman_Ford，具体采用哪种方法，视情况而定。

浙江大学城市学院实验报告
课程名称                    数据结构与算法
实验项目名称              实验八  图的最短路径问题
实验成绩          指导老师(签名 )               日期
实验目的和要求
掌握图的最短路径概念。
理解并能实现求最短路径的DijKstra算法(用邻接矩阵表示图)。
二. 实验内容
1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括：
① 初始化邻接矩阵表示的有向带权图 void InitMatrix(adjmatrix G);
② 建立邻接矩阵表示的有向带权图 void CreateMatrix(adjmatrix G, int n) (即通过输入图的每条边建立图的邻接矩阵);
③ 输出邻接矩阵表示的有向带权图void PrintMatrix(adjmatrix G, int n) (即输出图的每条边)。
把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。
2、编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组 path 和 dist 中。编写打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist[], edgenode *path[], int n)。
3、编写测试程序(即主函数)，首先建立并输出有向带权图，然后计算并输出从某顶点v0到其余各顶点的最短路径。
要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件test9_2.cpp中。
测试数据如下：
0
0
1
2
3
5
4
4
8
2
3
10
7
6
5
9
6
15
4、填写实验报告，实验报告文件取名为report8.doc。
5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。
三. 函数的功能说明及算法思路
包括每个函数的功能说明，及一些重要函数的算法实现思路
【结构说明】
const int MaxVertexNum=10; //图的最大顶点数
const int MaxEdgeNum=100;  //边数的最大值
const int MaxValue=32767; //权值的无穷大表示
typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵
typedef struct Node {
int  adjvex;
struct Node *next;
} edgenode;//路径结点
【函数说明】
① void  InitMatrix(adjmatrix &G)
功能：初始化邻接矩阵表示的有向带权图
思路：将邻接矩阵中的所有权值设置为无穷大(MaxValue)
② void  CreateMatrix(adjmatrix &G, int n)
功能：建立邻接矩阵表示的有向带权图(即通过输入图的每条边建立图的邻接矩阵)
思路：按照输入的顶点信息和权值信息，更新邻接矩阵内对应的值
③ void  PrintMatrix(adjmatrix G, int n)
功能：输出邻接矩阵表示的有向带权图 (即输出图的每条边)
思路：按照一定的格式输出邻接矩阵
④ void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n)
功能：求最短路径的DijKstra算法函数
思路：按照从源点到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度。设立一个集合S，用以保存已求得最短路径的终点，其初值为只有一个元素，即源点；一个数组 dist[n]，其每个分量 dist[j] 保存从源点经过S集合中顶点最后到达顶点 j 的路径中最短路径的长度，其初值为从源点到每个终点的弧的权值(没弧则置为∞)；一个指针数组path[n]，path[j]指向一个单链表，保存相应于dist[j]的从源点到顶点 j 的最短路径(即顶点序列)，初值为空。
⑤ void PATH(edgenode *path[], in

《《数据结构课程设计》最短路径问题实验报告》由会员分享，可在线阅读，更多相关《《数据结构课程设计》最短路径问题实验报告(17页珍藏版)》请在人人文库网上搜索。
1、目 录 一、概述1二、系统分析1三、概要设计2四、详细设计54.1建立图的存储结构54.2单源最短路径64.3任意一对顶点之间的最短路径7五、运行与测试8参考文献11附录12交通咨询系统设计(最短路径问题)一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等。
2、的一系列问题。二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。三、概要设计可以将该系统大致分为三个部分： 1 建立交通网络图的存储结构；2 解决单源最短路径问题；3 实现两个城市顶点之。
3、间的最短路径问题。交通咨询系统迪杰斯特拉算法(单源最短路径)费洛依德算法(任意顶点对间最短路径)建立图的存储结构义迪杰斯特拉算法流图：弗洛伊德算法流图：四、详细设计4.1建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息(下标为i的元素存储顶点的信息)。邻接矩阵的存储结构：#define MVNum 100 /最大顶点数typedef structV。
4、ertexType vexsMVNum;/顶点数组，类型假定为char型Adjmatrix arcsMVNumMVNum;/邻接矩阵，假定为int型MGraph;注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。4.2单源最短路径单源最短路径问题：已知有向图(带权)，期望找出从某个源点SV到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图G=(V,E)，其中V=1,2，n，cost是表示G的邻接矩阵，costij表示有向边的权。若不存在有向边，则costij 的权为无穷大(这里取值为32767)。设S是一个集合。
5、，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点V1为源点，集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离，其初值为disti= costij，i=2，n。从S之外的顶点集合V-S中选出一个顶点w，使distw 的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到S中包含V中其余顶点的最短路径。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到V中其。
6、余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。 4.3任意一对顶点之间的最短路径任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(VW)”，找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间的最短路径。费洛伊德算法的基本思想：假设求从Vi到Vj的最短路径。如果存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较路径和的路径长度，取。
7、长度较短者为当前所求得。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求得的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推直至顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间。
8、顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。五、运行与测试3测试实例1：利用如下图所示的有向图来测试13177161747632646456262455测试实例2：利用下图求交通网络图(无向图)的最短路径。2553北京西安70416952349徐州成都51181234郑州515796512368上海13857广州6实例1运行结果：实例2运行结果：六、总结与心得该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心的各种问题(当然此次试验最终主要解决的问题是：最短路径问题)。这次。
9、试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为重要。经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉算法、弗洛伊德算法等，对树的学习有了一个更深的了解。参考文献【1】数据结构严蔚敏.清华大学出版社.【2】数据结构课程设计苏仕华.极械工业出版社.附录#include#include#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;ty。
10、pedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G,int n,int e)int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;iarcsij=Maxint;printf(输入%d条边的i.j及w:n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕！n);void Dijkstra(MGraph *。
11、G,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;if(D2varcsvwarcsvw;p2w=v;printf(路径长度 路径n);for(i=1;iarcsij!=Maxint)pij=j;elsepij=0;Dij=G-arcsij;for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij) Dij=Dik+Dkj;pij=pik;void main()MGraph *G;int m,n,e,v,w,k;in。
12、t xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(输入图中顶点个数和边数n,e:);scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf(*求城市之间最短路径*n);printf(=n);printf(1.求一个城市到所有城市的最短路径n);printf(2.求任意的两个城市之间的最短路径n);printf(=n);printf(请选择 :1或2，选择0退出:n);scanf(%d,&xz);if (xz=2)Floyd(G,n);printf(输入源点(或起点)和终点:v,w:);scanf(%d,%d,&v,&w);k=pvw;if (k=0)printf(顶点%d 到 %d 无路径!n,v,w);elseprintf(从顶点%d 到 %d 最短路径路径是:%d,v,w,v);while (k!=w)printf(-%d,k);k=pkw;printf(-%d,w);printf(径路长度:%dn,Dvw);elseif(xz=1)printf(求单源路径，输入源点v :);scanf(%d,&v);Dijkstra(G,v,n);printf(结束求最短路径，再见!n。