一、定义

Dijkstra算法(迪杰斯特拉算法)是很有代表性的最短路径算法,用于计算一个结点到其他结点的最短路径。该算法指定一个点(源点)到其余各个结点的最短路径,因此也叫做单源最短路径算法。该算法是由荷兰计算机科学家Edsger W.Dijkstra于1959年发表。

Dijkstra算法是一种用于计算带权有向图中单源最短路径算法,不存在回溯的过程,因此它还不适用于带有负权重的情况。如果权值存在负数,那么被派生出来的可能是更短的路径,这就需要过程可以回溯,之前的路径需要被更短的路径替换掉,而Dijkstra算法是不能回溯的,它的每一步都是以当前最优选择为前提的。

Dijkstra算法的思想是广度优先搜索(BFS) 贪心策略。对于计算非加权图中的最短路径,也可使用BFS算法。Dijkstra算法是对BFS算法的推广,以起始点为中心向外层层扩展,并且每一次都选择最优的结点进行扩展,直到扩展到终点为止。Dijkstra算法可以划归为贪心算法,下一条路径都是由当前更短的路径派生出来的更长的路径。

Dijkstra算法在很多专业课程中都作为基本内容有详细的介绍,如数据结构、图论、运筹学等。

二、演示例子

例子1

第1步,创建距离表。第1列是结点名称,第2列是从起点A到对应结点的已知最短距离。开始我们并不知道A到其它结点的最短距离是多少,默认初始距离是无穷大。如图2-1-1所示:

迪杰斯特拉算法(dijkstra算法详细步骤)(1)

图2-1-1

第2步,遍历起点A的所有相邻结点,找到起点A的邻接结点B和C。从A到B的距离是5,从A到C的距离是2,刷新距离表中起点A到各结点的最短距离(绿色表示刷新)。如图2-1-2所示。

迪杰斯特拉算法(dijkstra算法详细步骤)(2)

图2-1-2

第3步,从图2-1-2距离表中找到从A出发距离最短的点,也就是结点C(最小距离是2)。遍历结点C的所有相邻结点,找到结点C的相邻结点D和F(A已经遍历过,不需要考虑)。从C到D的距离是1,所以A到D的距离是A-C-D=2 1=3;从C到F的距离是8;从A到F的距离是A-C-F=2 8=10。然后刷新距离表(绿色表示刷新)。如图2-1-3所示:

迪杰斯特拉算法(dijkstra算法详细步骤)(3)

图2-1-3

第4步,从图2-1-3距离表中找到从A出发距离最短的点(红色结点C已经遍历过,不需要考虑),也就是结点D(最小距离是3)。遍历结点D的所有相邻结点,找到相邻结点B、E和F(C已遍历过,不考虑)。从A-C-D-B的距离是3 1=4;从A-C-D-E的距离是3 1=4;从A-C-D-F的距离是3 2=5。刷新距离表中起点A到各结点的最短距离。如图2-1-4所示。

迪杰斯特拉算法(dijkstra算法详细步骤)(4)

图2-1-4

第5步,从图2-1-4距离表中找到从A出发距离最短的点(红色结点C、D已经遍历过,不需要考虑),也就是结点B和E(最小距离是4)。遍历结点B的所有相邻结点,找到相邻结点E(D遍历过,不考虑),从A-C-D-B-E的距离为10,比当前A到E的最小距离4要大,不考虑。遍历结点E的所有相邻结点,找到相邻结点G、B(D遍历过,不考虑),从A-C-D-E-G的距离为4 7=11<∞, 刷新距离表;A-C-D-E-B的距离4 6=10>4,不考虑。如图2-1-5所示。

迪杰斯特拉算法(dijkstra算法详细步骤)(5)

图2-1-5

第6步,从图2-1-5距离表中找到从A出发距离最短的点(红色结点B、C、D、E已经遍历过,不需要考虑),也就是结点F(最小距离是5)。从A-C-D-F-G的距离为8, 比当前最小距离11要小,刷新距离表。如图2-1-6所示。

迪杰斯特拉算法(dijkstra算法详细步骤)(6)

图2-1-6

就这样,除终点以外的全部结点都已经遍历完毕,距离表中存储的是从起点A到所有结点的最短距离。

例子2

图2-2-1是原始连通图。

迪杰斯特拉算法(dijkstra算法详细步骤)(7)

图2-2-1

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


步骤

集合S

集合Q

1

选择A到集合S={A}

此时最短路径A->A=0

以A为中间点,查找相邻点

Q={B,C,D,E,F,G}

A->-B=5

A->C=2

A->其它Q中结点=∞

发现A->C=2权值为最短

2

选择C到S={A,C}

此时最短路径A->A=0,A->C=2

以C为中间点,从A->C这条路径开始找

Q={B,D,E,F,G}

A->B=5(由第1步得到)

A->C->D=3

A->C->F=10

A->C->其它Q中结点=∞

在A到Q的结点中,发现A->C->D=3权值为最短

3

选择D到S={A,C,D}

此时最短路径A->A=0,A->C=2,A->C->D=3,

以D为中间点,从A->C->D这条路径开始找

Q={B,E,F,G}

A->C->D->B=4(比第1步的A->B=5要短,替换之)

A->C->D->E=4

A->C->D->F=5(比第2步的A->C->F=10要短,替换之)

A->C->D->G=∞

在A到Q的结点中,发现A->C->D->B=4或A->C->D->E=4权值为最短

4

选择B、E到S={A,C,D,B,E}

此时最短路径A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,

以B、E为中间点,分别从A->C->D->B、从A->C->D->E路径开始找

Q={F,G}

A->C->D->E->G=11

A->C->D->F=5(从第3步获得)

在A到Q的结点中,发现A->C->D->F权值为最短

5

选择F到S={A,C,D,B,E,F}

此时最短路径A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,A->C->D->F=5

以F为中间点,从,A->C->D->F这条路径开始找

Q={G}

A->C->D->F->G=8(比第4步的A->C->D->E->G=11要短,替换之)

6

选择G到S={A,C,D,B,E,F,G}

此时最短路径A->A=0,A->C=2,A->C->D=3,A->C->D->B=4,A->C->D->E=4,A->C->D->F=5,A->C->D->F->G=8

集合Q为空,查找完毕。


例子3

Dijkstra算法的执行过程:设初始集合S={s}, Q={t,y,x,z}. 源结点s为最左边的结点,每个结点中(圆圈中)的数值为该结点的最短路径的估计值(当前中间值)。黑色的结点属于集合S,白色的结点属于集合Q。每次从集合 S中选择最新加入的结点,分别计算并刷新与它直接相邻的结点的最短路径的估计值,然后从集合Q中选择最小估计值的结点,加入到集合S中。例如(b)中,集合Q中刷新后各结点的估计值为10,5,∞,∞,选择最小估计值为5的结点y,加入到集合S中, 接着计算并刷新结点y的相邻结点的最短路径的估计值。依次类推,直到集合Q中的所有结点全部加入到集合S中,算法结束。如图2-3-1所示。

迪杰斯特拉算法(dijkstra算法详细步骤)(8)

图2-3-1

三、应用

一切能抽象成图或树的场景,如果要求最短路径,Dijkstra算法可考虑。比如,查找两个城市之间的最短路径;在地图中寻找两个地点之间的最短路径;在网络连接中为路由器寻找最短的传输路径等。