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的最短路径是SBDT，SDT或SACET。

但由于"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