dijkstra算法的实现.doc

问题分析与任务定义 课程设计题目： 1.1题 目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。 1.2 要 求：对所设计的图的数据结构，提供必要的基本功能。 1.3具体任务：建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出来！ 2、问题原始数据的输入格式： 2.1建图模块：数字+空格+数字+空格+数字+回车 2.2插入和删除模块：以Y或者y，以N或者n按回车进入，然后雷同于建图模块 2.3显示模块：回车 3、实现功能： 3.1建立有向图 3.2排除和增加目的地，方便找出最短路径 3.3在建立好的有向图中，显示出来从顶点到各个顶点的最短路径 4、测试用例： 4.1正确数据：a）顶点：3；边值信息：0 1 2；1 0 3；1 2 5；2 1 6；0 0 0； b）顶点：0；边值信息：0 0 0； 4.2错误数据：a）顶点：#； b）顶点：3；边值信息：0 1 #； 4.3参考用图： 数据结构的选择和概要设计 数据结构的选择： 1.1对于最短路径问题： 最短路径（Shortest Path）是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径（source-sink），单源点的最短路径（single-source），所有点到所有点（all-pairs）以及带负边情况下的最短路径。用Dijkstra算法可以较好的解决单源点最短路径（无负边），其思想类似与求最小生成树（MST）的Prim算法。只是Dijkstra将优先队列的权由两点的边改为了从源点到下一点的路径：?Prim : Priority= edge.weight()??? ??? ??? ??? ??? ??? // 从v点到w点的weightDijkstra: Priority= wt[v] + edge.weight()?// 从源点到w点的值，wt[v]表示源点到v点的值Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：　　1) 初始化。起源点设置为： ds=0, ps为空; 所有其他点: di=∞, pi=?; 标记起源点s，记k=s,其他所有点设为未标记的。2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置： dj=min［dj, dk+lkj］ 式中，lkj是从点k到j的直接连接距离。3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i： di=min［dj, 所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置： i=j*　　5) 标记点i。如果所有点已标记，则算法完全出，否则，记k=i，转到2) 再继续。2.1结构图 2.2流程图 根据设计要求，流程图将分为：建图过程，插入顶点过程，删除顶点过程，显示邻接矩阵和求最短路径五个模块来写。 2.2.1建图过程 能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组，存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中，图的信息不是一成不变的，所以在实现初步输入图的信息后，要有删除和插入操作。需要插入顶点的时候，回归到初始建图模块，但是这个操作是在已建立的图上操作，而非在清除内存之后进行插入，所以，要实现插入的高效和实用性。在删除顶点的时候，在已建立的图上进行删除，首先对图进行遍历，只要是和欲删除的顶点有关联的边值都要删除掉，这样就实现了顶点的删除操作，目的是提高用户使用程序的效率，对已知或者误录入的顶点进行排除，增加了程序的人性化。 2.2.2插入顶点过程 插入顶点模块，主要是重新申请空间，在已建立的图上增加顶点，并处理增加顶点和原图各顶点之间的关系，最后进入到删除顶点模块。 2.2.3删除顶点过程 2.2.4显示邻接矩阵 显示邻接矩阵是建图过程终结的标志，所以，从三个模块汇总到最终的显示，功能上又有了些许区别。 2.2.5Dijkstra算法求最短路径 Dijkstra算法的实现主要是以广度遍历的方法对图进行筛选最短路径的点，并保存在一个数组里面，构成一条最短路径。 详细设计和编码 3.1 Dijkstra 求最短路径的基本思想 把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递