Dijkstra最短路径算法，如果有相同距离的路径怎么办？

Question

在这个网络中，使用Dijkstra的最短路径算法。问题是A将使用哪条路径到达D，因为它们都相等？

那个表缺失了吗？

- makkuzu

---

为什么这很重要（既然它们是相等的）？ - user529758

这是实现细节。无论哪种方式都可以。 - Benjamin Gruenbaum

这是一份作业，A是否会在其表中添加双向？ - makkuzu

Answer 1

这取决于您的实际实现方式以及输入图的描述方式（例如，边可以按不同顺序排列，如果有许多边，则会对结果产生影响）。

但是，保证它将找到某条具有最优长度的路径。

您的表格在E和F顶点处似乎有误。E的父顶点是D（AB->BD->DE = 3 + 4 + 2 = 9），F也是如此。

- dreamzor

---

那么，在这个作业中，我应该将B和C都添加为到达D的下一个路由器吗？ - makkuzu

确实，否则你怎么知道C-D边的长度不是1呢？ - dreamzor

它要求从A到所有网络节点的最短路径。 - makkuzu

如果您知道从A到D的最短路径的长度，那么在A->D->...->VERTEX具有最优长度的情况下，无论您实际上使用哪条路径从D到其他顶点都没有关系。只需从队列中选择一个最终顶点并继续前进即可。 - dreamzor

很抱歉，我有点困惑，所以我已经在上面的问题中添加了我的表格。现在，在这个表格中，我还应该再次添加目标D，为此下一个路由器将是C，成本为7，对吗？ - makkuzu

不一定，D处的单个B就可以了。如果有多条最优路径，则选择哪个特定的顶点并不重要。 - dreamzor

Answer 2

这要看放松函数的实现方式。例如，维基百科中描述的算法 严格使用小于比较运算符：“if alt < dist[v]”，因此在此情况下（以及我所见到的所有实现中），从 A 到 D 的最短路径是 A -> B -> D。

为什么呢？因为（其中 S 表示已确定的节点，Q 表示节点队列，由距离和父节点组成）：

1. 开始松弛 A，使得 S = {A:0} 和 Q = {B:3,A C:5,A D:9,A}
2. 从 Q 中选择 B 并松弛它。你会得到 S = {A:0 B:3,A} 和 Q = {C:(5,A) D:7,B E:10,B}
3. 从 Q 中选择 C 并松弛它。你会得到 S = {A:0 B:3,A C:5,A} 和 Q = {D:7,B E:10,B}。
4. 从 Q 中选择 D，算法就完成了。

请注意，在步骤 3 中，你不需要更改 D 的父节点，因为新路径不比当前路径更好。如果松弛算法使用的是“小于或等于”的比较方式，那么结果将会不同。

- Javier