Dijkstra算法不生成最短路径？(Dijkstra's Algorithm Does n

我使用Dijkstra算法通过最短路径问题的工作。 我有麻烦，因为算法应该提供的最短路径，但算法运行后我拿到手短路路径。 这仅仅是这个算法的副产品？

我想产生的路径是从 - >ž

下面是我从应用的算法，采取在每个顶点我访问的最短距离跳跃获取路径：

  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。

我有没有失误的地方？

Answer 1:

看起来你误会Dijkstra算法是如何工作的。 而不是采取具有最小重量边缘在每个节点上，你总是需要考虑从一开始（节点$ A $）的总距离。 你保持所有可能的路径在考虑一个堆，它开始了作为刚刚开始节点，没有边，并通过添加与添加到您当前正在考虑在每一步路节点的每一个外出边缘的所有路径扩展。

这也就是说试图总结你在哪里错了的混乱。 我建议重读Dijkstra算法如何工作的： http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

文章来源: Dijkstra's Algorithm Does not generate Shortest Path?