题目:Dijkstra 算法的实现
一、 问题分析和任务定义
1.1 题 目:对任意图,选择合适的数据结构表示图,在此基础上实现求解最短路
径的 Dijkstra 算法。
1.2 要 求:对所设计的图的数据结构,提供必要的基本功能。
1.3 具体任务:建立图的表示模块,顶点的插入和删除操作模块;在建立图之后从
单源点开始求最短路径,并显示出最短路径长度及路径途径!
2、实现功能:
2.1 建立有向图
2.2 在建立好的有向图中,显示出来从源点到其他各个顶点的最短路径长度及路径途
径。
3、测试用例:
3.1 正确数据:a)顶点:3;边值信息:0 1 2;1 0 3;1 2 5;2 1 6;0 0 0;
b)顶点:0;边值信息:0 0 0;
3.2 错误数据:a)顶点:#;
b)顶点:3;边值信息:0 1 #;
3.3 参考用图:图 1
图 1. 有向图
问题分析: 题目要求选择合适的数据结构表示图,本程序邻接矩阵存储结点和弧等图的有
关信息
对用邻接矩阵表示的有向图,从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无
路径?最短路径是什么?路径长为多少?问题要求写一个程序从有向网中的某一顶点出发
0
1
2
2
3
1
2
5
4