algorithm - Dijkstra：在有向图中查找最短路径

Question

考虑下图所示的有向图。顶点 S 和 T 之间存在多条最短路径。Dijstra 的最短路径算法会报告哪一条？假设在任何迭代中，只有在发现到 v 的严格更短的路径时，才会更新到顶点 v 的最短路径。

我的答案是 SBDT 但在解决方案中它给了 SACET 我不知道为什么..

Answer 1

Dijkstra 算法选择节点如下：

B(3) from S
A(4) from S
C(5) from A
E(6) from C
D(7) from S or B
G(8) from E
T(10) from D or E

因此，到 的最短路径T是或。SBDTSDTSACET

但是由于"the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered"，当E被访问时，T的最短路径的先前节点将被设置为E并且不再改变。

因此答案是SACET。

Answer 2

在http://dracos.co.uk/maths/dijkstra/中运行它， 答案是 SDT。原因：在节点S之后，考虑它的直接邻居即：A(4),D(7),B(3) 现在考虑这些节点的直接邻居。我们在考虑节点 C 之前到达 SDT(10)，因为 C 不是 S 的直接邻居。答案：SDT