Dijkstra算法设计与实现

杜衡吉

摘要：最短路径算法在各领域应用广泛，大多《离散数学》的图论部分最短路径算法讲解较为粗略，不便于学生学习和实践。经过多年教学总结，对最短路径算法给出设计和实现，有利于学生对本知识的掌握和实践应用。

关键词：最短路径；离散数学； Dijkstra算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）28-0079-02

1 概述

最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值之和最小的路径。Dijkstra 算法在很多计算机专业可均有介绍，如数据结构，离散数学等，但大都比较粗略。迪克斯特拉算法是经典的求解最短路径问题的方法，是按路径长度递增的次序来产生最短路径的算法[1]。

最短路径问题描述：设n，m带权图 G=，V={v0，v1，…，vn-1}，E={e1，e2，…，em}，其中假设每条边ei 的权值为 wi，单源的最短路径就是从图G中找到起源点 V0 到图中其余各点的最短路径。

2 最短路径概念

带权图G=， 其中W：ER， eE，w（e）称作e的权。 若vi和vj相邻e=（vi，vj）， 记w（vi，vj）=w（vi，vj） ， 若vi，vj不相邻， 记w（vi，vj）=。通路L的权是指L的所有边的权值之和， 记作w（L），u和v之间的最短路径指的是 u和v之间边权最小的通路[2]。

3 Dijkstra算法描述

1）算法基本过程：设带权图G=，把图G中顶点集合V分成两个子集，第一个子集是已求出最短路径的顶点集合，用V1表示，初始化时V1中只有一个起源点，以后每求得一条最短路径 ， 就将被选定点加入到集合V1中，直到图中全部顶点都依次添加到到V1中，算法就结束了；第二个集合为G中其余未确定最短路径的顶点集合，用V2表示，按最短路径长度的递增次序依次把第二个集合V2中的被选顶点加入集合V1中。特别，在加入的过程中，总保持从起源点v0到V1中各顶点的最短路径长度不大于从源点v0到V2中任何顶点的最短路径长度。此外，每个顶点对应一个距离，V1中的顶点的距离就是从v0到此顶点的最短路径长度，V2中的顶点的距离，是从v0到此顶点只包括V1中的顶点为中间顶点的当前最短路径长度。

2）算法具体步骤：

a.初始时，V1只包含源点，即V1={ v0}，v0的距离为0。V2包含除v0外的其他顶点，即： V2={ v1， v2…，vn-1}。定义集合V2中的顶点的距离：若v0与V2中顶点v有边，则dist（v）=w（v0，v）正常有权值，若v0与v点不相邻，则dist（v）= ∞。

b.从V2中选取一个点k加入V1中，选择公式dist（k）=min（dist（v） | v∈U），把k加入V1中（该选定的距离就是v0到k的最短路径长度）。此时V1= V1∪{k}，同时V2集合中删除k点，即V2= V2-{k}。

c.以k为新考虑的中间点，修改V2中各顶点的距离；若从源点v0到顶点v的距离（经过顶点k）比原来距离短，则修改顶点 v的距离值，否则v的距离值不变，修改公式dist（v）=min{dist（v），dist（k）+dist（k，v）}[3]。

d.重复步骤b和c直到V1=V，算法停止。

4 算法实例

1）先给出一个无向图G=，如图1所示：

用Dijkstra算法找出以A为起点的单源最短路径步骤如表1：

5 算法代码实现

测试案例如图2所示：

#include

#include

#define M 100

#define N 100

using namespace std；

typedef struct node

{int m[N][M]； //邻接矩阵

int n； //顶点数

int e； //边数

}MGraph；

void Dpath（MGraph g，int *dist，int *path，int v0） //v0表示源点

{int i，j，k；

bool *ved=（bool *）malloc（sizeof（bool）*g.n）；

for（i=0；i

{if（g.m[v0][i]>0&&i！=v0）

{dist[i]=g.m[v0][i]；

path[i]=v0； } //path记录最短路径上从v0到i的前一个顶点

else

{dist[i]=INT_MAX； //若i不与v0直接相邻，则权值置为无穷大

path[i]=-1； }

ved[i]=false；

path[v0]=v0；

dist[v0]=0； }

ved[v0]=true；

for（i=1；i

{int min=INT_MAX；

int u；

for（j=0；j

{if（ved[j]==false&&dist[j]

{ min=dist[j]；

u=j；} }

ved[u]=true；

for（k=0；k

{ if（ved[k]==false&&g.m[u][k]>0&&min+g.m[u][k]

{dist[k]=min+g.m[u][k]；

path[k]=u； }}}}

void Apath（int *path，int v，int v0） //打印最短路径上的各个顶点

{stack s；

int u=v；

while（v！=v0）

{ s.push（v）；

v=path[v]； }

s.push（v）；

while（！s.empty（））

{cout<

s.pop（）；}}

int main（int argc， char *argv[]）

{ int n，e； //表示输入的顶点数和边数

while（cin>>n>>e&&e！=0）

{int i，j；

int s，t，w； //表示存在一条边s->t，权值为w

MGraph g；

int v0；

int *dist=（int *）malloc（sizeof（int）*n）；

int *path=（int *）malloc（sizeof（int）*n）；

for（i=0；i

for（j=0；j

g.m[i][j]=0；

g.n=n；

g.e=e；

for（i=0；i

{cin>>s>>t>>w；

g.m[s][t]=w； }

cin>>v0； //输入源顶点

Dpath（g，dist，path，v0）；

for（i=0；i

{if（i！=v0）

{ Apath（path，i，v0）；

cout<

return 0； }

测试结果如图3所示：

6 小结

作为一门计算机的专业基础课《离散数学》在计算机学科领域中发挥了重要的作用。最短路径算法在很多方面有着重要的应用，针对教材中Dijkstra最短路径算法讲解粗略，学生学习困难等问题，本人结合多年的教学经验，对Dijkstra算法求最短路径给出了详细的算法设计和实现，对这部分内容的教学帮助明显。

参考文献：

[1] 李妍妍.Dijkstra最短路径分析算法的优化实现[J].测绘与空间地理信息，2014，37（5）：172-190.

[2] 耿素云，屈婉玲，张立昂.离散数学[M]. 5版.北京：清华大学出版社，2013：128-130.

[3] 曹晓东，原旭.离散数学及算法 [M].北京：机械工业出版社，2012：240-244.