如果2个图节点之间的间接路径比直接路径短，Dijkstras算法可以检测到吗？

Question

Dijkstras 算法根据起始节点和中间节点之间的边权重假定最近邻。重复此过程直到到达目标节点。

如果起始节点和中间节点之间的最短路径是通过其他几个中间节点的间接路由怎么办？

Answer 1

我认为您不太了解该算法的工作原理。是的，它首先检查最近的邻居——但它仍然检查所有其他邻居，它不会仅仅因为它们不是最近的就丢弃它们。如果最短路径确实通过间接路径，那么沿该路径的每个节点的总距离必然比较长的直接路径更短，因此先被访问。需要在算法输入中禁止负权重来确保这一点。

Answer 2

What if the shortest path between start node and an intermediate node is an indirect route through several other intermediate nodes?

尝试找到最短路径时，通常会遇到穿越多个节点的情况。如果没有多个可能的路径，那你为什么需要 Dijkstra？

想象下图：

为了更好地理解，假设算法从顺时针方向开始，从 START 开始到 1 节点。它会发现 START -> 1 -> 6 -> END 花费 7。然后它会逆时针走，发现 START -> 3 -> 5 -> 8 -> 9 -> END 花费 5。然后算法会将逆时针路径标记为从 START 得到的最短路径至 END.

现在假设我们有下图：

算法会发现 START -> 1 -> 9 花费 5（顺时针）而 START -> 3 -> 5 -> 8 -> 9 花费 4（逆时针）。因此，该算法会将逆时针路径标记为从 START 到 END 的最短路径，成本为 5。接下来，该算法将尝试找到另一条（如果可能的话更短）通过 [=12] 的路径=].它将发现这条路径花费 4，并将这条路径标记为从 START 到 END.

的最短路径

Answer 3

采用括号中每条边的成本的简单图形：

   _____ (5)
  /     \
Root   Dest
  \__A__/
 (2)    (1)

然后 Dijkstra's algorithm using a min-priority queue 将：

从根开始，将所有相邻边形成的路径放入队列：
queue = [(root-A : 2), (root-dest : 5)]
从队列中删除成本最低的路径：
- 请注意，这是第一次访问 A，因此到达 A 的最低成本是 2（如果任何后续的、成本更高的路径到达 A 然后他们可以被忽略）。
- 将该路径和相邻边形成的所有路径放入队列中：
  queue = [(root-A-dest : 3), (root-dest : 5)]
从队列中删除成本最低的路径：
- 请注意，这是第一次访问 dest，因此到达 dest 的最低成本是 3。
- 已到达目的地，算法将停止。

因此，对于最小优先级队列，如果通过间接顶点的路径比直接路径更短，则直接边可以在队列中保持未处理状态。

If the indirect path between 2 graph nodes is shorter than the direct path, can Dijkstras algorithm detect it?

是的，上面的例子表明它会。

如果2个图节点之间的间接路径比直接路径短，Dijkstras算法可以检测到吗？

If the indirect path between 2 graph nodes is shorter than the direct path, can Dijkstras algorithm detect it?

graph-theory

dijkstra