Dijkstra's 算法不生成最短路径? [英] Dijkstra's Algorithm Does not generate Shortest Path?

问题描述

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

我试图生成的路径来自 a -> 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.

我是不是走错了地方?

推荐答案

您似乎误解了 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_算法

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

这篇关于Dijkstra's 算法不生成最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！