dijkstra算法的实现__精品.doc

合肥学院 题目: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. 有向图 问题分析: 题目要求选择合适的数据结构表示图，本程序邻接矩阵存储结点和弧等图的有关信息 对用邻接矩阵表示的有向图，从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵arsc[n][n]中的每一个元素只能有三种情况： ① 当i=j 时，p[i][j]=0; ② 当顶点i到j无边时，p[i][j]= MAX; ③ 当顶点i到j 有边且权值为arcs[i][j]时，p[i][j]= arcs[i][j]. 由于题目中没有规定输出格式，本程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度。 二、数据结构的选择和概要设计 1) 数据存储结构 以邻接矩阵存储有向图，如图2中有向图G所示，其邻接矩阵为图 3 arcs。 图2. 有向图 图3.矩阵arcs 有向图的邻接矩阵arcs[i][j]定义为 int arcs[n][n]; 2)概要设计 对用邻接矩阵表示的有向图，从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵arsc[n][n]中的每一个元素只能有三种情况：① 当i=j 时，p[i][j]=0; ② 当顶点i到j无边时，p[i][j]= MAX; ③ 当顶点i到j 有边且权值为arcs[i][j]时，p[i][j]= arcs[i][j]. 建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出来！ 流程图如图4 图4.程序流程图 （2) 设计表示法 (1) 函数调用关系如图11.2所示。 (2) 函数接口说明。 void ShortesPath(MGraph *G,int v0,int h) int v,D[20],p[20][20],w,i,min,final[20],t=0; char P[20][20]; char p1[2]; p1[1]=\0; p1[0]=G-vexs[v0]; /* 求n个顶点，邻接矩阵为arcs，从源点v0到各顶点的最短路径，D[ ]记载从源点到其余各顶点的最短路径长度, min=D [ ]为最短路径, 数组P[ ][ ]用来存储顶点，若P[v][w]为1，则w是从v0到v当前求的最短路径的顶点,final[v]为1当且仅当，即已求的从v0到v的最短路径。 (3)各部分的函数和各函数之间的关系 采用邻接矩阵表示法，构造有向图 typedef struct ArcCell //定义顶点类型 typedef struct //定义图的类型 int LovateVex(MGraph *G,char v) //顶点定位函数 void Create(MGraph *G) 采用数组(邻接矩阵)表示法，构造无向网G. void ShortesPath(MGraph *G,int v0,int h) 用Dijkstra算法求有向图的G的V0顶点到其余顶点V的最短路径 void main() (4) 实现注释 (1) 系统限定邻接矩阵的阶n不超过20； (2) 为方便起见，系统假设有向网中边的权为整型数； (3) 若有向网中顶点i到j之间无边，则取值1000。 Dijkstra算法描述如下： (1) 输入顶点个数n，邻接矩阵arcs