Dijkstra算法和贪婪策略

Question

我似乎很难理解贪婪策略是如何工作的，以及Dijkstra算法是如何跟踪最短路径的。作为参考，以下是Dijkstra算法的伪代码

DijkstrasAlgorithm(G, w, s)
InitalizeSingleSource(G, s)
S = 0
Q = G.V
while Q != 0
u = ExtractMin(Q)
S = S∪{u}
for each vertex v ∈ G.Adj[u]
Relax(u, v, w)

请考虑以下重量方向图。

有5个顶点：s、t、x、y、z有10条边：

s->t = 3
s->y = 5
t->y = 2
t->x = 6
y->t = 1
y->x = 4
y->z = 6
x->z = 2
z->x = 7
z->s = 3

我们的目标是找到从s到x的最短路径。我的答案是s->t->y->x，长度为9，我假设伪代码中的"s"是最短路径，并且minQ中的每个ExtractMin都被添加到该路径上。

然而，我的老师告诉我这是错误的。正确答案是s->t->x，长度为9。我们答案的区别在于是否包括y。我的老师说，由于s->t->x是"最先找到的"，所以它不会更新为s->t->y->x，它的长度相等。

这让我很困惑。Dijkstra的算法使用了贪婪策略，我认为贪婪策略总是选择当时可用的最短路径。当选择是在t->y和t->x之间时，t->y更短，因此应该被选取。

我的问题是：

1( 在什么情况下，贪婪策略不会为最终结果选择最短的路径？

2( 如果在minQ上使用ExtractMin不是我们跟踪从s到x的整体路径的方式，那么我们如何跟踪完整路径？

Answer 1

老师的答案假设我们按照"先短后破"的顺序探索路径。

首先，我们探索s->t，我们将成本为9的x从s->t->x放在"某一天"要探索的事物列表中。但我们首先探索s->t->y是因为它更短。在这一点上，我们看到s->t->y->x是一个选项，成本也是9。然而，因为这不是一个改进，我们放弃了它

因此，一旦我们找到长度为9的路径，我们就会发现s->t->x是out，因为它首先进入队列。

如果你修改Relax以保存一条可能的路径，如果它优于或等于迄今为止发现的最佳路径，你就会得到答案。这会得到一个正确的答案。

至于路径是如何从末端提取的，每个节点都知道你是如何到达它的。所以从末端开始，沿着cookie轨迹反向找到路径，然后反向得到实际路径。