Dijkstra算法

龙源期刊网

Dijkstra算法设计与实现

作者：杜衡吉

来源：《电脑知识与技术》2016年第28期

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

关键词：最短路径；离散数学； 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中的顶点为中间顶点的当前最短路径长度。 龙源期刊网

最短路径——dijkstra算法代码（c语⾔）

最短路径问题

看了王道的视频，感觉云⾥雾⾥的，所以写这个博客来加深理解。（希望能在12点以前写完）

（）

⼀、总体思想

1.初始化三个辅助数组

s[],dist[],path[]

s[]:这个数组⽤来标记结点的访问与否，如果该结点被访问，则为1，如果该结点还没有访问，则为0；

dist[]:这个数组⽤来记录当前从v到各个顶点的最短路径长度，算法的核⼼思想就是通过不断修改这个表实现；

path[]:这个数组⽤来存放最短路径；

2.遍历图，修改上⾯的各项数组，每次只找最短路径，直到遍历结束

⼆、代码实现

1 void dijkstra(Graph G, int v)

2 {

3 int s[G.vexnum];

4 int dist[G.vexnum];

5 int path[G.vexnum];

6 for(int i = 0; i < G.vexnum; i++)

7 {

8 s[i] = 0;

9 dist[i] = G.edge[v][i];

10 if(G.edge[v][i] == max || G.edge[v][i] == 0)

11 {

12 path[i] = -1;

13 }

14 else

15 {

16 path[i] = v;

17 }

18 s[v] = 1;

19 }

20

21 for(int i = 0; i < G.vexnum; i++)

22 {

23 int min = max;

24 int u;

25 for(int j = 0; j < G.vexnum; j++)

26 {

27 if(s[j] != 1 && dist[j] < min)

28 {

29 min = dist[j];

30 u = j;

31 }

32 }

33 s[u] = 1;

34 for(int j = 0; j < G.vexnum; j++)

35 {

36 if(s[j] != 1 && dist[j] > dist[u] + G.edge[u][j])

Dijkstra算法（Dijkstra算法）由荷兰计算机科学家Dikstra于1959年提出，因此也称为Dikstra算法。从一个顶点到其余顶点的最短路径算法解决了权利图中的最短路径问题。 Dijestela算法的主要特征是从起点开始，采用贪婪算法的策略。每次，它都会遍历最接近且未访问过的顶点的相邻节点，直到起点为止。

Dijkstra的算法通常以两种方式表示，一种使用永久和临时标签，另一种使用OPEN和CLOSE表，两者都使用永久和临时标签。请注意，该算法不需要图形中的负边缘权重。

1.首先，引入一个辅助数组（向量）D，其中每个元素D代表当前找到的

Dijkstra运行动画过程

Dijkstra运行动画过程

从起点（即源点）到其他每个顶点的长度。

例如，D = 2表示从起点到顶点3的路径的相对最小长度为2。这里的重点是相对的，这意味着D在算法执行期间近似于最终结果，但不一定相等执行期间的长度。

2. D的初始状态为：如果存在一个从to的弧（即，存在一个从to的连接边），则D是弧上的权重（即，从to的边的权重）；否则，将D设置为无穷大。

显然，长度为D = Min {D | ∈V}是从起点到顶点的最短路径，即（）。

3.那么，下一个最短的长度是？即找到与从源点到下一顶点

的最短路径长度相对应的顶点，并且该最短路径长度仅次于从源点到顶点的最短路径长度。

假设子短路径的终点是，则可以想象路径是（）或（）。它的长度是从PI到PI的弧上的权重，或者是D加上从PI到PI的弧上的权重。

4.通常，假定S是从源点获得的最短路径长度的一组顶点，则可以证明下一条最短路径（令其终点为）是arc（）或仅从源点穿过中间的S顶点，最后到达顶点。

因此，具有较短长度的下一个最短路径长度必须为D = Min {D

| ∈v-s}，其中D是arc（）上的权重，或者D（∈S）和arc（，）上的权重之和。

该算法描述如下：

1）让圆弧代表圆弧上的重量。如果弧不存在，则将弧设置为无穷大（在这种情况下为MAXCOST）。 S是从起点出发的集合，初始状态为空集合。然后，从顶点到图的其余部分的每个顶点的可能长度的初始值为D = arcs [Locate Vex（G，）]，∈V;

迪克斯特拉算法：

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

定义：

Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

算法思想：

按路径长度递增次序产生算法：

把顶点集合V分成两组：

（1）S：已求出的顶点的集合（初始时只含有源点V0）

（2）V-S=T：尚未确定的顶点集合

将T中顶点按递增的次序加入到S中，保证：

（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度 依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。

（反证法可证）

求最短路径步骤

算法步骤如下：

G={V,E}

1.初始时令S={V0},T=V-S={其余顶点}，T中顶点对应的距离值

若存在，d(V0,Vi)为弧上的权值

若不存在，d(V0,Vi)为∞

2.从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中

3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止