Dijkstra算法求解最短路径的设计与实现

作者：刘敏

来源：《电脑知识与技术》2012年第12期

        摘要：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。对所设计的图的数据结构，提供必要的基本功能。建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径并显示。实现的功能有建立有向图，排除和增加目的地，方便找出最短路径，在建立好的有向图中，显示出来从顶点到各个顶点的最短路径。

        关键词：最短路径；有向图；数据结构

        中图分类号：TP313文献标识码：A文章编号：1009-3044(2012)12-2759-03

        1设计问题的提出

        1.1对于最短路径问题

        最短路径是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径，单源点的最短路径，所有点到所有点以及带负边情况下的最短路径。

        1.2 Dijkstra算法的主要思想

        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概要设计

        在任意图中实现求最短路径问题,首先是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径，所以，建立图这一步很关键。在实际使用当中，顶点的信息是成千上万，而且是随时可能产生变动，故建图模块要实现顶点的删除和插入操作；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能，这也是程序实际化的要求。

        3建图过程

        能把一个带有顶点和权值的数据结构图输入电脑首先要用到数组，存储每个顶点信息以及每两个顶点构成的线路的权值。在建图的过程中，图的信息不是一成不变的，所以在实现初步输入图的信息后，要有删除和插入操作。需要插入顶点的时候，回归到初始建图模块，但是这个操作是在已建立的图上操作，而非在清除内存之后进行插入，所以，要实现插入的高效和实用性。在删除顶点的时候，在已建立的图上进行删除，首先对图进行遍历，只要是和欲删除的顶点有关联的边值都要删除掉，这样就实现了顶点的删除操作，目的是提高用户使用程序的效率，对已知或者误录入的顶点进行排除，增加了程序的人性化。

        4 Dijkstra求最短路径的基本思想

        把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。

        4.1 Dijkstra求最短路径的步骤

        设图以邻接矩阵cost存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。从顶点v1到其它各顶点间的最短路径的具体步骤如下：

        1）初始化：s[MAX]。设一dist向量，其下标是各顶点，元素值是顶点v0到各顶点的边的权值。若v0到某顶点无边，dist向量中的对应值为无穷大。

        2）选dist中最小的权值，将其顶点s[V0]加入s集合。

        3）修改从顶点V0到集合s[MAX]中各顶点的最短路径长度,如果

        dist[u]+cost[u][j]

        则修改dist[k]为

        dist[k]=dist[u]+cost[u][j]

        4)重复（2）、（3）n-1次。由此求得v1到图上其余各顶点得最短路径。

        4.2存储结构体：用于存储经过的顶点和顶点数以及权值

        struct

        {int num;

        int pnode[MAX]; }path[MAX]; //path为从V0到各顶点的最短路径

        4.3建图子函数：

        void creatgraph()//创建带权有向图

        { int i,j,s,e,len,contin=1;

        printf("请输入点个数:");

        scanf("%d",&n); for(i=0;i

        {for(j=0;j

        cost[i][j]=up;

        cost[j][i]=up；}

        cost[i][i]=0;}

        4.4显示所建的邻接矩阵图

        void display(int n1)//显示用户输入的信息

        { int i,j;

        printf("\\n********所建图的邻接矩阵*******\\n____");

        for(i=0;i

        printf("____%d____",i);

        printf("\\n");

        for(i=0;i

        {

        printf("%d",i);

        for(j=0;j

        printf("\%6d<%d,%d>",cost[i][j],i,j);

        printf("\\n");

        4.5求最短路径模块

        void shortdjs()//求最短路径

        { int s[MAX];

        int mindis,dis,i,j,v0=0,u=0;

        for(i=0;i

        { dist[i]=cost[v0][i];//初始化dist[]数组

        path[i].pnode[0]=v0;//顶点都为0

        path[i].num=0;//记录经过的结点数都为0

        s[i]=0;}

        4.6输出最短路径

        void dispath()//输出最短路径

        {{printf("(V0->%d): ",i);

        if(dist[i]

        printf("\ %d\(",dist[i]);

        else

        printf("\∝\(");//显示无穷大

        for(j=0;j

        printf("V%d->",path[i].pnode[j]);

        printf("V%d>\\n",path[i].pnode[path[i].num]);}

        }

        在这里还没有设计建图过程中，顶点的插入和删除功能，这两个功能可加到Creargraph（）中。

        5结束语

        这个程序广泛用在社会交通当中，用v0~V20表示不同的地点信息，供出行者参考，具体使用方法如下：

        1）输入顶点个数：最大不能超过20，请输入罗马数字，若输入其他符号，会显示警告；

        2）以“数字数字数字”的格式输入图的信息，第一次输入的第一个数字为源点，也就是我们的出发点，求最短路径会从这个顶点开始，每一次输入的第二个数字也是顶点，第三个数字是前两个顶点间的距离，或者说是权值，当输入“0 0 0”时，将停止录入功能；

        3）在录入图的信息之后，屏幕中会出现一个矩阵来核实用户录入的图正确与否，程序将会提示用户是否进行添加顶点，如果想添加顶点请按“Y”或者“y”，若不添加顶点请按“N”或“n”退出添加顶点系统；

        4）添加顶点的过程和Step1中录入方式相同，同样以“0 0 0”结束录入。这时系统将提醒用户是否要删除顶点，以防止误入图的信息；

        5）类似于Step3中方法进入删除顶点信息，系统根据用户输入的顶点序号删除其对应的所有信息，在完成修改之后系统将显示顶点到其他各点的最短路径，以供用户查询参考。

        参考文献：

        [1]王昆仑,李红.数据结构与算法[M].北京：中国铁道出版社,2006.

        [2]苏仕华.数据结构与算法解析[M].合肥:中国科学技术大学出版社,2004.

        [3]王昆仑,李红.数据结构与算法[M].北京:中国铁道出版社,2007.

        [4]郭嵩山.国际大学生程序设计竞赛例题解[M].北京:电子工业出版社,2008.

        [5]刘大有,唐海鹰.数据结构[M].北京:高等教育出版社,2001.

        [6]徐孝凯.数据结构实用教程[M].北京:清华大学出版社,1999.

        [7]严蔚敏,陈文博.数据结构及算法教程[M].北京:清华大学出版社,2001.

        [8]刘振安,刘燕君. C程序设计课程设计[M].北京:机械工业出版社,2004.