dijkstra算法的实现

《dijkstra算法的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、问题分析与任务定义1、课程设计题目：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在建

2、立好的有向图中，显示出来从顶点到各个顶点的最短路径4、测试用例：4.1正确数据：a）顶点：3；边值信息：012；103；125；216；000；b）顶点：0；边值信息：000；4.2错误数据：a）顶点：#；b）顶点：3；边值信息：01#；4.3参考用图：V0V1V2231254二、数据结构的选择和概要设计1、数据结构的选择：1.1对于最短路径问题：最短路径（ShortestPath）是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径（source-sink），单源点的最短路径（single-source），所有点到所有点（all-p

3、airs）以及带负边情况下的最短路径。1.2Dijkstra算法用于求最短路径：用Dijkstra算法可以较好的解决单源点最短路径（无负边），其思想类似与求最小生成树（MST）的Prim算法。只是Dijkstra将优先队列的权由两点的边改为了从源点到下一点的路径： Prim:Priority=edge.weight()                  //从v点到w点的weightDijkstra:Priority=wt[v]+edge.weight() //从源点到w点的值，wt[v]表示源点到v点的值1.3Dijkstra算法的主要思想Dij

4、kstra算法的基本思路是：假设每个点都有一对标号(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)选取下一

5、个点。从所有未标记的结点中，选取dj中最小的一个i：di=min［dj,所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*　　5)标记点i。如果所有点已标记，则算法完全退出，否则，记k=i，转到2)再继续。1、概要设计在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径，所以，建立图这一步很关键，是Dijks

6、tra算法实现的一个必经之路，而且图的建立过程应该是能够与用户互动的。在实际使用当中，顶点的信息是成千上万，而且是随时可能产生变动，故建图模块要实现顶点的删除和插入操作；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能，对用户达到一个互动的目的，这也是程序实际化的要求。YYNN建图增加顶点删除顶点Dijkstra算法求最短路径显示最短路径输入顶点与边值信息定义顶点个数开始结束2.1结构图2.2流程图根据设计要求，流程图将分为：建图过程，插入顶点过程，删除顶点过程，显示邻接矩阵和求最短路径

7、五个模块来写。2.2.1建图过程能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组，存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中，图的信息不是一成不变的，所以在实现初步输入图的信息后，要有删除和插入操作。需要插入顶点的时候，回归到初始建图模块，但是这个操作是在已建立的图上操作，而非在清除内存之后进行插入，所以，要实现插入的高效和实用性。在删除顶点的时候，在已建立的图上进行删除，首先对图进行遍历，只首先初始化数组，让两点之间的权值为最大，各点到自身为零NNNYYYYN开始插入顶点判断输入s、e、len为零否用for(i=0;i

8、