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 的最短路径。我的答案是长度为 9 的 s->t->y->x，我假设伪代码中的 "S" 是最短路径，并且将来自 minQ 的每个 ExtractMin 添加到路径中。

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

这让我很困惑。 Dijkstra's Algorithm 使用的是贪心策略，当时我以为贪心策略就是总是选择最短的可用路径。 And when the the choice is between t->y and t->x, t->y is shorter and should therefore be picked.

我的问题是：

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

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

Answer 1

您老师的回答假设我们按顺序探索路径，"shortest first, broken by first seen first"。

首先我们探索 s->t，我们将 x 的成本 9 从 s->t->x 放入要探索的事物列表 'some day'。但是我们首先探索 s->t->y 因为它更短。那时，我们看到 s->t->y->x 是一个选项，成本也是 9。但是因为这不是改进，我们放弃了它。

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

如果您修改 Relax 以保存可能的路径（如果它优于或等于目前找到的最佳路径），您将得到答案。这将得到正确答案。

至于路径是怎么提取到最后的，每个节点都知道你是怎么弄到的。所以从最后开始，沿着cookie的踪迹向后走，找到反向的路径，然后反向得到实际的路径。

Dijkstra 算法和贪心策略

Dijkstra's Algorithm and the greedy strategy

c++

algorithm

dijkstra