【数据结构算法】实验8 图的最短路径问题(附源代码).doc

《【数据结构算法】实验8 图的最短路径问题(附源代码).doc》由会员分享，可在线阅读，更多相关《【数据结构算法】实验8 图的最短路径问题(附源代码).doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验八 图的最短路径问题 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1. 掌握图的最短路径概念。2. 理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。 二. 实验内容1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括： 初始化邻接矩阵表示的有向带权图 void InitMatrix(adjmatrix G); 建立邻接矩阵表示的有向带权图 void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）; 输出邻接矩阵表示的有向

2、带权图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、。3、编写测试程序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点v0到其余各顶点的最短路径。要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件test9_2.cpp中。测试数据如下：01235448231076596154、填写实验报告，实验报告文件取名为report8.doc。5、上传实验报告文件report8.doc与源程序文件test9_2.cpp及Graph2.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算

4、法实现思路【结构说明】const int MaxVertexNum=10; /图的最大顶点数const int MaxEdgeNum=100; /边数的最大值const int MaxValue=32767; /权值的无穷大表示typedef int adjmatrixMaxVertexNumMaxVertexNum; /邻接矩阵 typedef struct Node int adjvex; struct Node *next; edgenode;/路径结点【函数说明】 void InitMatrix(adjmatrix &G)功能：初始化邻接矩阵表示的有向带权图思路：将邻接矩阵中的所有权值

5、设置为无穷大（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算法函数思路：按照从源点

6、到其余每一顶点的最短路径长度递增的次序依次求出从源点到每个顶点的最短路径及长度。设立一个集合S，用以保存已求得最短路径的终点，其初值为只有一个元素，即源点；一个数组 distn，其每个分量 distj 保存从源点经过S集合中顶点最后到达顶点 j 的路径中最短路径的长度，其初值为从源点到每个终点的弧的权值（没弧则置为）；一个指针数组pathn，pathj指向一个单链表，保存相应于distj的从源点到顶点 j 的最短路径（即顶点序列），初值为空。 void PATH(edgenode *path, int i, int j)功能：将pathi的路径改为pathj的路径+i思路：分为三个步骤：一，删

7、除pathi中原来保存的链表；二，将pathj的路径复制给pathi；三，将j结点加入pathi的路径中 void PrintPath(int dist, edgenode *path, int n)功能：打印输出从源点到每个顶点的最短路径及长度的函数思路：按照一定的格式遍历输出从源点到每个顶点的最短路径及长度四. 实验结果与分析包括运行结果截图等【测试数据】0123544823107659615顶点数：7输入弧的信息：尾顶点头顶点权值01803512214102462553133573615659正确的邻接矩阵应为：842106537159下面以测试数据为基准，给出DijKstra算法生成最

8、短路径的状态变化图：（注：顶点旁边的代表当前状态下从源点到该顶点的最短路径长度）012354486 012354437615【状态】 【状态】 012354423107615 01235442376615【状态】 【状态】 01235442376615 01235442376615【状态】 【状态】 01235442376615【状态(最短路径)】五. 心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】Test9_2.cpp#include#include#include#include#includeGraph2.htypedef struct

9、Node int adjvex; struct Node *next; edgenode;void main()int n;adjmatrix G;edgenode *pathMaxVertexNum;int distMaxVertexNum;void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n);void PrintPath(int dist, edgenode *path, int n);InitMatrix(G);printf(输入要构造的图顶点数n);scanf(%d,&n);CreateMatrix(G

10、,n);PrintMatrix(G,n); /打印图的邻接矩阵coutendlendl*以下为DijKstra算法部分*endlendl;Dijkstra(G, dist, path, 0, n);PrintPath(dist,path,n);/求最短路径的DijKstra算法函数void Dijkstra( adjmatrix GA, int dist, edgenode *path, int i, int n)int j,k;int v = 1,minIndex;void PATH(edgenode *path, int i, int j);bool *isStepped;/初始化部分/i

11、sStepped：申请n个空间，除i以外均为false/dist：邻接矩阵中i顶点到各顶点的距离/path：邻接矩阵中i顶点到各顶点若有路径，则保存；无路径置为NULLisStepped = new booln;for (j = 0; j adjvex = i;pathj-next = new edgenode;pathj-next-adjvex = j;pathj-next-next = NULL;else pathj = NULL;isSteppedj = false;isSteppedi = true;while(v = n)/尝试查找当前最小路径结点，用minIndex保存顶点minI

12、ndex = i;for (k = 0; k n; k+)if (distk distminIndex & (!isSteppedk)minIndex = k;/有查找到最小路径顶点，则将其并入集合if (minIndex != i)isSteppedminIndex = true;/未查找到，则说明路径都为，退出elsebreak;/通过while中确定的最小路径顶点（minIndex）到达当前顶点/若路径长度小于dist中保存的路径长度，则修改for (k = 0; k n; k+)if (GAminIndexk + distminIndex next;delete pathi;pathi

13、 = p;/将pathj的路径复制给pathip = new edgenode;p-adjvex = pathj-adjvex;pathi = p;t = pathj-next;while (t != NULL)q = p;p = new edgenode;p-adjvex = t-adjvex;q-next = p;t = t-next;/将j结点加入pathi的路径中q = p;p = new edgenode;p-adjvex = i;p-next = NULL;q-next = p;/打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist, edg

14、enode *path, int n)int i;edgenode *p;for (i = 1; i n; i+)cout vi endl;cout最短路径：;p = pathi;if (p = NULL)cout无路径！endlendl;continue;while( p != NULL)coutvadjvexnext;coutendl最短长度：distiendlendl;Graph2.hconst int MaxVertexNum=10; /图的最大顶点数const int MaxEdgeNum=100; /边数的最大值const int MaxValue=32767; /权值的无穷大表示

15、typedef int adjmatrixMaxVertexNumMaxVertexNum; /邻接矩阵 /初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrix &G)int i,j; for (i=0; iMaxVertexNum; i+) /邻接矩阵初始化 for (j=0; j头顶点名，权值 输入数据，以0-0,0结尾:如A-B,23 n);while(true) /构造邻接矩阵 scanf(%d-%d,%d,&v,&w,&q); /输入弧的两个定点及该弧的权重getchar();if (v = 0 & w = 0 ) break; if( v = n | w

16、 = n) cerrvertex ERROR!;exit(1); Gvw=q; /输出邻接矩阵表示的有向带权图 （即输出图的每条边）void PrintMatrix(adjmatrix G, int n)int i,j;coutendl-endl;coutYour Graph is:endlendl; for (i=0; in; i+) for (j=0; jn; j+) if(Gij!=MaxValue) printf( %2d | ,Gij);else printf( | ); printf(n);26) ) ),| ) +;= + ;= - , 边每出输权有表接出; ) ! | = |0

17、 0= 0= )( 权弧点个的/; ,%-( 矩接构/ ) ) ,-:0-以数 ，顶-点：照 , ) & 阵矩邻边每输即权向表接邻 ; )+; 0 始初接/ + ;= & ( 权带的阵邻 阵/; 表大值/; = 大的/ 0 点大图 ： -= ) ( 径无 ) = ：短 - ) ! - 制路 = - =) ( 链存原除 * ) , ( +路 径 + ) , ) + ( )+ = = - = - = )= ) 0= 径无则，有到点中接 距距到 矩： 均以除个： 部始 ) , ( , ) , ( 函函 的短) ) 0 , , *分算 下* 矩邻的打 ( ), )&% )点顶构 )( ) , * ,

18、) )( * . . . 短路、困办和等 . . ( ,*, (构 & 打 *下 *= )最用存 ; ( ) 查将 = 未径 确 顶保则 ) + , + 路( , *除原链 =- = 制 ! -点 径 =从顶函 * ;+ 径 () 0的 大 阵 邻的 ( ; 0 );接向即边 ) 照：顶以- )矩 -, 点弧 0 | | ;出权输 - 0 为应接 权顶顶息信： 函度及短的个从输) , ( 径的 入 三 给径路 二链存来 删，个分+径 为路 将 , 空空初列（路 到源 应存表个 指个为则（弧终到从值度径最路的顶后最集经从保 个其 个点元一为初点短求存，集立度径路点个源出序增度最点余到从函算 短求

19、 , 矩矩输定按边每的（权有的接输 值应阵接更值和顶输按阵矩的立条入过图向表阵立 & （穷设值的矩邻权向示表接 & ( 明明数结路; ; 矩/ 表穷的/ 大大边 0= 点大图/; 明明构思现的函些，能数括 思法说能函下件己器 _ 程 . 件报传 . 件文验告 中 头存作操及定结）每即) , 带的矩接;阵接图建图过（ , ( 带有示接; 图有阵邻始括括基，的操图图有表接写内内。）阵邻用 的最实念念最的要要 签老 绩 路最 名 与结 报实学学 学 绩 最实的 ）内写图操括始 示有 图接接带 ,每结及作 件 传 程_ 件能思数些现明 /图 = 大 穷表 数 示邻设（ 阵过立阵顶和接 输权每边矩 , 求 从点度出点度，点为点 保经后路度终弧为 存到 空 径分删存 径 输个短 ：息 接26