algorithm - 尝试通过一个简单示例了解 Dijkstra 算法的工作原理

Question

我想通过较短的路线(成本最低)从 a 到 d

  1    15
a--->b---->d
|        /\
|2       /
|       /1
|      /
|     /
|    /
|   /
|  /
| /
\/
c

a 可以以 1 的成本转到 b 或以 2 的成本转到 c。b 可以以 15 的成本转到 d。c 可以以 1 的成本转到 d。

算法不会以 a->b 开始，因为它的成本为 1 而 a->c 的成本为 2？但是它只能以 15 的成本从 b->d 开始，这比从 a->c->d

开始的成本更高>

我正在努力更新这个算法，所以请告诉我我的逻辑是否有缺陷。

Answer 1

在第一步中，找到节点与“a”的暂定距离，即 s(b)= 1 和 s(c) =2

队列 --> s(b) = 1, s(c) = 2

现在从优先级队列中取出我们得到 b，所以再次计算暂定距离 s(d)= 16

队列 --> s(c) = 2, s(d) =16

现在出列我们得到 c，所以计算与 c 的暂定距离，s(d) =3 > 先前值 s(d)=17

所以最短距离是3