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

但是由于 “只有当发现到 v 的严格更短路径时，才会更新到顶点 v 的最短路径”，当 E 被访问，T 的最短路径的优先节点将被设置为 E 并且不再改变。

因此答案是SACET。