当边在 dijkstra 算法中具有相同的权重时，下一个顶点是什么？

Question

   2    3
A____B______C
|           |
|3          |5
|           |
D___________E
       5

当图如上，我想求从A到E的最短路径

首先，我从 A 开始并将（B 和 D）的距离更新为（2 和 3）。然后，边的最小距离是2所以我移动到B.

我的问题是哪个是下一个顶点，因为 A-D 的距离与 B-D 的距离相同...

Answer 1

这里是计算距离AE的所有步骤。您可以将每个距离初始化为 Infinity，并从 distance AA = 0 开始。在每一步选择与 A 距离最小的候选者。如果邻居尚未被访问，则更新其与 A 的邻居距离。重复该过程，直到访问 E。

从 A 开始（距离 = 0）。

 1. Distance to B (through A) = 0 + 2 = 2.
 2. Distance to D (through A) = 0 + 3 = 3.

sortedCandidates = [B=2, D=3]

选择B（距离=2）。

 1. Distance to C (through B) = 2 + 3 = 5.

sortedCandidates = [D=3, C=5]

选择D（距离=3）。

 1. Distance to E (through D) = 3 + 5 = 8.

sortedCandidates = [C=5, E=8]

选择C（距离=5）。

 1. Distance to E (through C) = 5 + 5 = 10 (reject as it is more than 8).

sortedCandidates = [E=8]

选择E（距离=8）。

 1. Do nothing.

距离AE = 8

What would be the next vertex when the edges have the same weights in dijkstra algorithm?