algorithm - Dijkstra 算法不生成最短路径？

Question

我正在使用 Dijkstra 算法解决最短路径问题。我遇到了麻烦，因为该算法应该提供最短路径，但是在运行该算法后，我手动得到了一条短路路径。这只是该算法的副产品吗？

我试图生成的路径来自 a -> z

无标记图

这是我应用算法得到的路径，在我访问的每个顶点处采取最短距离跳跃：

  2    4    2    2    1    2    1    1    8      = 23
a -> d -> g -> k -> r -> n -> q -> p -> t -> z

标记图

这让我很困惑，因为如果我走这条路：

  4    2    2    2    2    2    2     = 16
a -> c -> f -> i -> m -> p -> s -> z

我得到的距离比算法生成的距离小 5。

我是不是在什么地方走错了？

score 3 · Accepted Answer

看起来您误解了 Dijkstra 算法的工作原理。而不是在每个节点上取权重最小的边，你总是需要考虑到起点（节点$a$）的总距离。您维护一个正在考虑的所有可能路径的堆，它从没有边的起始节点开始，并通过添加所有路径来扩展，节点的每个传出边都添加到您当前正在考虑的每个步骤的路径中。

那是一堆乱七八糟的词，试图总结你哪里出错了。我建议重新阅读 Dijkstra 算法的工作原理：http ://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

1 回答 1