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

I am working through a shortest path problem using Dijkstra's Algorithm. I am having trouble because the algorithm is supposed to provide the shortest path, but after running the algorithm I get a shorted path by hand. Is this just a by-product of this algorithm?

我想生成的路径是从 - >以Z

The path I am trying to generate is from a -> z

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

Here is the path that I get from applying the algorithm, taking the shortest distance jump at each vertex I visit:

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

这是令人困惑的我，因为如果我走这条路：

This is confusing to me because if I take this path:

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

我得到一个距离，该距离比从算法生成的距离5以下。

I get a distance that is 5 less than the distance generated from the algorithm.

我有没有失误的地方？

Did I misstep somewhere?

推荐答案

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

Looks like you misunderstand how Dijkstra's algorithm works. Instead of taking the edge with the smallest weight at each node, you always need to consider the total distance from the beginning (node $a$). You maintain a heap of all possible paths under consideration, which starts off as just the starting node with no edges and expands by adding all the paths with each outgoing edge of a node added to the path you're currently considering at each step.

这是尝试的话来概括，你错在哪里的混乱。我建议重读如何Dijkstra算法的工作原理： http://en.wikipedia.org/wiki/Dijkstra ％27s_algorithm

That's a jumble of words trying to summarise where you went wrong. I suggest re-reading how Dijkstra's algorithm works: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm