c++ - Dijkstra的算法和贪婪策略

我似乎有点难以理解贪婪策略是如何工作的，以及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的整个路径，那么我们如何跟踪整个路径？

最佳答案

你老师的回答是假设我们按照“最短优先，被最先看到的先打破”的顺序探索道路。
从探索开始，我们以9美元的价格将s->t从x放到探索“某一天”的清单上。但我们首先探索s->t->x是因为它更短。在这一点上，我们看到s->t->y是一个选项，也是成本9然而，因为这不是一个改进，我们放弃它。
因此，当我们到达长度为9的路径时，我们会发现s->t->y->x是因为它首先进入队列。
如果修改s->t->x以保存一条可能的路径（如果该路径优于或等于迄今为止找到的最佳路径），您将得到答案这会得到一个正确的答案。
至于如何从末端提取路径，每个节点都知道如何到达因此，从末尾开始，沿着cookie路径向后寻找反向路径，然后反向找到实际路径。

关于c++ - Dijkstra的算法和贪婪策略，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53603011/