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的每个minQ都添加到了路径中。

然而，我的老师告诉我，这是错误的。正确的答案是s->t->x，长度9。我们答案的不同之处在于是否包含y。我的老师说，由于s->t->x是“先发现的”，所以它不会更新为s->t->y->x，它的长度相同。

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

我的问题是：

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

2)如果在ExtractMin上使用minQ并不能跟踪从s到x的整个路径，那么我们如何跟踪整个路径呢？

Answer 1

您的老师的回答假设我们探索路径的顺序，“最短的第一，打破第一次看到第一”。

为了开始探索s->t，我们将x从s->t->x的成本9放到了“有朝一日”的探索列表中。但是我们首先探索s->t->y，因为它更短。在这一点上，我们看到s->t->y->x是一个选择，成本也是9。然而，因为这不是一个改进，所以我们放弃了它。

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

如果您修改Relax以保存一个可能的路径，如果它优于或等于到目前为止找到的最佳路径，您就会得到答案。这会得到一个正确的答案。

至于路径是如何从末端提取的，每个节点都知道如何到达它。因此，从末尾开始，按照cookie跟踪向后找到反向路径，然后反转它以获得实际路径。