【图论】Dijkstra算法求最短路

一、Dijkstra算法简介

Dijkstra算法是由河南荷兰计算机科学家狄克斯特拉(Dijkstra)于1959年提出的,因此又叫狄克斯特拉算法。

二、初识Dijkstra算法

在使用Dijkstra算法求最短路时，需要用到三个辅助数组：
$vi{s}_x$：布尔数组，给 $x$ 号结点打标记。初始化为 $0$。
$ste{p}_x$：记录从固定起点到 $x$ 号结点的最短路径，初始化为 $+\infty$。
$pr{e}_x$：记录 $x$ 号结点的前一个结点，如果不理解前一个结点是什么意思，第三部分模拟过程中会讲解。

三、模拟Dijkstra算法求最短路径长度

首先看下面的图5。

图5

假设我们要求从 $0$ 号结点到 $4$ 号结点的最短距离，下面是模拟过程：

1. 初始化 $vis$ 和 $step$ 数组，记录起点$ste{p}_0=0$；
2. 找到目前未被标记的 $step$ 值最小的结点 $0$，标记 $vi{s}_0=1$，$0$ 号结点的邻接点有 $1$ 和 $7$，边权分别为 $4$ 和 $8$，记录 $ste{p}_1=min(ste{p}_1,ste{p}_0+4)=4$，$ste{p}_7=min(ste{p}_7,ste{p}_0+8)=8$，$pr{e}_1=0$，$pr{e}_7=0$；
3. 找到目前未被标记的 $step$ 值最小的结点 $1$，标记 $vi{s}_1=1$，$1$ 号结点的邻接点有 $2$ 和 $7$，边权分别为 $8$ 和 $11$，记录 $ste{p}_2=min(ste{p}_2,ste{p}_1+8)=12$，$ste{p}_7=min(ste{p}_7,ste{p}_1+11)=8$，$pr{e}_2=1$（PS：此处因为 $8\le 15$，所以无需对 $ste{p}_7$ 和 $pr{e}_7$ 的值进行修改）；
4. 找到目前未被标记的 $step$ 值最小的结点 $7$，标记 $vi{s}_7=1$，$7$ 号结点的邻接点有 $1$、$6$ 和 $8$，边权分别为 $11$、$1$ 和 $7$，记录 $ste{p}_1=min(ste{p}_1,ste{p}_7+11)=4$，$ste{p}_6=min(ste{p}_6,ste{p}_7+1)=9$，$ste{p}_8=min(ste{p}_8,ste{p}_7+7)=15$，$pr{e}_6=7$，$pr{e}_8=7$；
5. 找到目前未被标记的 $step$ 值最小的结点 $6$，标记 $vi{s}_6=1$，$6$ 号结点的邻接点有 $5$、$7$ 和 $8$，边权分别为 $2$、$1$ 和 $6$，记录 $ste{p}_5=min(ste{p}_5,ste{p}_6+2)=11$，$ste{p}_7=min(ste{p}_7,ste{p}_6+1)=8$，$ste{p}_8=min(ste{p}_8,ste{p}_6+6)=15$，$pr{e}_5=6$；
6. 找到目前未被标记的 $step$ 值最小的结点 $5$，标记 $vi{s}_5=1$，$5$ 号结点的邻接点有 $2$、$3$、$4$ 和 $6$，边权分别为 $4$、$14$、$10$ 和 $2$，记录 $ste{p}_2=min(ste{p}_2,ste{p}_5+4)=12$，$ste{p}_3=min(ste{p}_3,ste{p}_5+14)=25$，$ste{p}_4=min(ste{p}_4,ste{p}_5+10)=21$，$ste{p}_6=min(ste{p}_6,ste{p}_5+2)=9$，$pr{e}_3=5$，$pr{e}_4=5$；
7. 找到目前未被标记的 $step$ 值最小的结点 $2$，标记 $vi{s}_2=1$，$2$ 号结点的邻接点有 $1$、$3$、$5$ 和 $8$，边权分别为 $8$、$7$、$4$ 和 $2$，记录 $ste{p}_1=min(ste{p}_1,ste{p}_2+8)=4$，$ste{p}_3=min(ste{p}_3,ste{p}_2+7)=19$，$ste{p}_5=min(ste{p}_5,ste{p}_2+4)=11$，$ste{p}_8=min(ste{p}_8,ste{p}_2+2)=14$，$pr{e}_3=5$，$pr{e}_8=2$；
8. 找到目前未被标记的 $step$ 值最小的结点 $8$，标记 $vi{s}_8=1$，$8$ 号结点的邻接点有 $2$、$6$ 和 $7$，边权分别为 $2$、$6$ 和 $7$，记录 $ste{p}_2=min(ste{p}_2,ste{p}_8+2)=12$，$ste{p}_6=min(ste{p}_6,ste{p}_8+6)=9$，$ste{p}_7=min(ste{p}_7,ste{p}_8+7)=11$；
9. 找到目前未被标记的 $step$ 值最小的结点 $3$，标记 $vi{s}_3=1$，$3$ 号结点的邻接点有 $2$、$4$ 和 $5$，边权分别为 $7$、$9$ 和 $14$，记录 $ste{p}_2=min(ste{p}_2,ste{p}_3+7)=12$，$ste{p}_4=min(ste{p}_4,ste{p}_3+9)=21$，$ste{p}_5=min(ste{p}_5,ste{p}_3+7)=14$；
10. 找到目前未被标记的 $step$ 值最小的结点 $4$，标记 $vi{s}_4=1$，$4$ 号结点的邻接点有 $3$ 和 $5$，边权分别为 $9$ 和 $10$，记录 $ste{p}_3=min(ste{p}_3,ste{p}_4+9)=19$，$ste{p}_5=min(ste{p}_5,ste{p}_4+10)=11$；
11. 此时我们发现，所有结点都已经被标记过，结束搜索，起点 $0$ 到终点 $4$ 的最短距离为 $ste{p}_4=21$。

四、模拟Dijkstra算法求最短路径

仍以上面的图5为例，搜索过程略。
从终点 $x=4$ 往回遍历，每遍历到一个结点就将其入栈，然后 $x=pr{e}_x$。当遍历到起点 $0$ 入栈后，结束遍历，输出栈。
得到结果 $0\to 7\to 6\to 5\to 4$。
代码将于2024年九月底完成，目前不予展示。
如果博客有错误，请联系我，我会尽快修正！鲁A济南车！