当前位置：首页 > news >正文

【图论】Dijkstra算法求最短路

news 来源：原创 2024/9/19 9:25:44

一、Dijkstra算法简介

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

二、初识Dijkstra算法

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

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

首先看下面的图5。

图5

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

初始化 $v i s$ 和 $s t e p$ 数组，记录起点 $step_0=0$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $0$ ，标记 $vis_0=1$ ， $0$ 号结点的邻接点有 $1$ 和 $7$ ，边权分别为 $4$ 和 $8$ ，记录 $step_1=min(step_1,step_0+4)=4$ ， $step_7=min(step_7,step_0+8)=8$ ， $pre_1=0$ ， $pre_7=0$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $1$ ，标记 $vis_1=1$ ， $1$ 号结点的邻接点有 $2$ 和 $7$ ，边权分别为 $8$ 和 $11$ ，记录 $step_2=min(step_2,step_1+8)=12$ ， $step_7=min(step_7,step_1+11)=8$ ， $pre_2=1$ （PS：此处因为 $\leq 15$ ，所以无需对 $step_7$ 和 $pre_7$ 的值进行修改）；
找到目前未被标记的 $s t e p$ 值最小的结点 $7$ ，标记 $vis_7=1$ ， $7$ 号结点的邻接点有 $1$ 、 $6$ 和 $8$ ，边权分别为 $11$ 、 $1$ 和 $7$ ，记录 $step_1=min(step_1,step_7+11)=4$ ， $step_6=min(step_6,step_7+1)=9$ ， $step_8=min(step_8,step_7+7)=15$ ， $pre_6=7$ ， $pre_8=7$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $6$ ，标记 $vis_6=1$ ， $6$ 号结点的邻接点有 $5$ 、 $7$ 和 $8$ ，边权分别为 $2$ 、 $1$ 和 $6$ ，记录 $step_5=min(step_5,step_6+2)=11$ ， $step_7=min(step_7,step_6+1)=8$ ， $step_8=min(step_8,step_6+6)=15$ ， $pre_5=6$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $5$ ，标记 $vis_5=1$ ， $5$ 号结点的邻接点有 $2$ 、 $3$ 、 $4$ 和 $6$ ，边权分别为 $4$ 、 $14$ 、 $10$ 和 $2$ ，记录 $step_2=min(step_2,step_5+4)=12$ ， $step_3=min(step_3,step_5+14)=25$ ， $step_4=min(step_4,step_5+10)=21$ ， $step_6=min(step_6,step_5+2)=9$ ， $pre_3=5$ ， $pre_4=5$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $2$ ，标记 $vis_2=1$ ， $2$ 号结点的邻接点有 $1$ 、 $3$ 、 $5$ 和 $8$ ，边权分别为 $8$ 、 $7$ 、 $4$ 和 $2$ ，记录 $step_1=min(step_1,step_2+8)=4$ ， $step_3=min(step_3,step_2+7)=19$ ， $step_5=min(step_5,step_2+4)=11$ ， $step_8=min(step_8,step_2+2)=14$ ， $pre_3=5$ ， $pre_8=2$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $8$ ，标记 $vis_8=1$ ， $8$ 号结点的邻接点有 $2$ 、 $6$ 和 $7$ ，边权分别为 $2$ 、 $6$ 和 $7$ ，记录 $step_2=min(step_2,step_8+2)=12$ ， $step_6=min(step_6,step_8+6)=9$ ， $step_7=min(step_7,step_8+7)=11$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $3$ ，标记 $vis_3=1$ ， $3$ 号结点的邻接点有 $2$ 、 $4$ 和 $5$ ，边权分别为 $7$ 、 $9$ 和 $14$ ，记录 $step_2=min(step_2,step_3+7)=12$ ， $step_4=min(step_4,step_3+9)=21$ ， $step_5=min(step_5,step_3+7)=14$ ；
找到目前未被标记的 $s t e p$ 值最小的结点 $4$ ，标记 $vis_4=1$ ， $4$ 号结点的邻接点有 $3$ 和 $5$ ，边权分别为 $9$ 和 $10$ ，记录 $step_3=min(step_3,step_4+9)=19$ ， $step_5=min(step_5,step_4+10)=11$ ；
此时我们发现，所有结点都已经被标记过，结束搜索，起点 $0$ 到终点 $4$ 的最短距离为 $step_4=21$ 。

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

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