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

首页
迪杰斯特拉算法dijkstra算法详细步骤迪杰斯特拉(Dijkstra算法

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

2022-07-20 19:31:07 网络知识 官方管理员

178|0条评论

一、定义

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

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

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

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

二、演示例子

例子1

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

图2-1-1

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

图2-1-2

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

图2-1-3

第4步，从图2-1-3距离表中找到从A出发距离最短的点（红色结点C已经遍历过，不需要考虑），也就是结点D（最小距离是3）。遍历结点D的所有相邻结点，找到相邻结点B、E和F（C已遍历过，不考虑）。从A-C-D-B的距离是31=4；从A-C-D-E的距离是31=4；从A-C-D-F的距离是32=5。刷新距离表中起点A到各结点的最短距离。如图2-1-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的距离为47=11<∞,刷新距离表;A-C-D-E-B的距离46=10>4,不考虑。如图2-1-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所示。

图2-1-6

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

例子2

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

图2-2-1

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

步骤

集合S

集合Q

选择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权值为最短

选择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权值为最短

选择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权值为最短

选择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权值为最短

选择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要短，替换之)

选择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所示。