Dijkstra的算法不会生成最短路径？

Question

我正在通过使用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