我想通过较短的路线（最低成本）从a到到d
1 15
a--->b---->d
| /\
|2 /
| /1
| /
| /
| /
| /
| /
| /
\/
c
a可以以b1c的成本或 2 的成本
b去。可以以d15 的成本
c去。可以以d1 的成本去。
算法会不会a->b因为它的成本为 1 而不是a->c成本为 2 而开始？但是它只能b->d以 15 的成本离开，这比从a->c->d
我正在尝试更新这个算法，所以请告诉我我的逻辑是否有缺陷。
在第一步中，找到节点到“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
错误是认为“第一种方式，最好的方式”，这是不正确的。在此算法中，您可以更新到达顶点的成本（如果成本较低的话）。
节点分为已访问、未访问、可用、不可用。
我们不能考虑visited，因为如果，他的值最小，而且我们没有负值边（见算法假设）你就找不到更好的方法。
未访问的都是另一回事，可能我们实际上无法走到所有这些地方。
可用的顶点都是未访问的，我们现在可以访问。（我认为，不可用是显而易见的。）
开始时可用的只有第一个顶点。我们可以遵循一个简单的模式。
一步步：
- 从所有（实际）可用的顶点中获取最便宜的顶点。这应该由优先级队列完成。最简单的解决方案是二叉堆（O(|E| log |V|)），但是如果您考虑性能，可以使用斐波那契堆（O(|E|+|V|log|V|)），如果不要，可能，但不推荐的方法是使用数组（O(|V|^2+E)）。这应该是根。
-对于当前节点，您应该更新所有未访问的邻居（未访问的，不可用的（为什么，见上文））行程成本如果（（当前节点的成本+连接它们的边缘的权重，与邻居）<（实际成本从开始节点到达邻居））。当您将不可用更改为可用时，您必须将更改的元素添加到优先级队列中。当你更新一个节点的成本时，你应该升级堆，不要忘记。
- 将实际节点标记为已访问。将他从优先级队列中删除（永久地，它被访问过），在最小堆中它是 delete_root 操作。
- 重复直到队列不为空。
在您的示例中，它可能如下所示：
Number - 实际上是节点之间路径的最低总权重（第一个和最后一个）。
星星 - 节点被访问，这个成本永远不会改变。
Dash - 节点此时不可用。
| a | b | c | d |
-----------------
| 0 | - | - | - | <-- Available is only a.
-----------------
|*0*| 1 | 2 | - | <-- You can go to b and c.
-----------------
|*0*|*1*| 2 | 16| <-- b was cheaper, you updated costs from this vertex.
-----------------
|*0*|*1*|*2*| 3 | <-- You didn't stop, and find less costly way!
-----------------
|*0*|*1*|*2*|*3*| <-- Work done, the last vertex visited.
-----------------
更具体地说，最初可用的只是第一个元素，所以一开始你必须拜访他。完成后，可用的是两个新节点，您应该访问最便宜的（从可用，未访问）。是b。从 b 到 d 是唯一的方式，所以你只升级他的成本（现在 d 可用，但实际方式（成本）可能不是最优的）。再次从可用的顶点中获取最便宜的顶点。是 c，因为访问了 a 和 b，并且 2 小于 16。当您检查此节点时，您会找到更好的方法 d，因此您应该将 d 的成本从 16 更新为 3。访问的最后一个节点 (d) 是正式且无关紧要的移动。您访问了所有顶点，现在您的工作已经完成。
每次算法访问一个节点时，它都会将其所有邻居（尚未访问的）放入优先级队列中。优先级队列保持元素按最小成本排序，因此总是首先计算最短距离。
所以要回答你的问题，它从 a->b 开始，然后是 a->c，然后是 b->d，然后是 c->d。
如果你想加速算法，我建议你用二进制堆来实现算法。本质上它所做的是它总是用一个非常基本的搜索来测试下一个可能成本最低的节点。
http://algorithms.soc.srcf.net/notes/dijkstra_with_heaps.pdf