Dijkstra's Algorithm Does not generate Shortes

问题:

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?

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

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

Did I misstep somewhere?

回答1:

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.

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