Dijkstra算法背部追踪？ [英] Dijkstra's algorithm with back tracking?

问题描述

在<一个href="http://stackoverflow.com/questions/28333756/finding-most-efficient-path-between-two-nodes-in-an-interval-graph/28333937#28333937">related线程，有人建议我impliment Dijkstra算法寻找在图形上的最短路径。望着这.gif注意的算法，从维基百科：

In a related thread, it was suggested that I impliment Dijkstra's algorithm for finding the shortest path on a graph. Looking at this .gif of the algorithm from wikipedia:

如果有什么路径1,3,6,5被证明是非常低的成本？例如，在3-6重量为1，并在6-5重量为2？ Dijkstra算法不会考虑这条道路，因为它只是看起来领先一步;它跳过节点3

What if the path 1,3,6,5 turned out to be very low cost? For example, the weight on 3-6 was 1, and the weight on 6-5 was 2? Dijkstra's algorithm would not consider this path because it only looks one step ahead; it skipped node 3.

是可以接受指定的参数，使算法看2,3,4 ...... n步提前选择每一个节点之前？我知道这可能炸掉计算时间，但只要节点不是非常密集的（即每个节点不超过3个或4个连接），这可以为我们特定的数据集提供的性能和最佳的解决方案之间的一个体面的权衡。

Is it acceptable to specify a parameter that makes the algorithm look 2,3,4...n steps ahead before choosing each node? I realize that this could potentially blow up computational time, but as long as the nodes aren't very dense (ie not more than 3 or 4 connections per node), this could provide a decent tradeoff between performance and optimal solution for our specific dataset.

有没有人有这种强烈的感受？而就是这样与此可调参数可能在图形软件包或不是最短路径算法？

Does anyone have strong feelings about this? And is such a shortest-path algorithm with this adjustable parameter likely to be in graph packages or not?

推荐答案

Dijkstra算法总能找到最短路径（图中没有负沿），从不回溯。这是很容易推理吧。

Dijkstra algorithm always finds the shortest path (in graphs without negative edges) and never backtracks. It is easy to reason about it.

想想一个节点，它的边缘（这是一个更大的图形只是其中的一部分）：

Think about a node and its edges (it's just part of a larger graph):

    6   _ 3
    |  /
  14| /9
    |/
    1-------2
        7  

Dijkstra算法将开始选择边 1-2（7）。我这样做是因为它是最小的也有过这么远。然后，它设置的最短路径为 2 的值 7 。它绝不会再次改变这个值，因为任何其他的路径从 1 到 2 要大（因为它必须启动同一条边 1-3（9）或 1-6（14））。

Dijkstra's algorithm will begin choosing the edge 1-2 (7). I does so because it is the minimum it has seen so far. It then sets the value of the shortest path to 2 as 7. It will never change this value again, because any other path from 1 to 2 must be larger (as it must start with one of the edges 1-3 (9) or 1-6 (14)).

来思考下一步怎么走的一种方法是pretend算法合并已知的节点到一个单一的。在这个例子中，只要最短路径 2 选择，它结合了 1 和 2 作为一个单一的逻辑节点。所有的边缘走出去 2 都增加了 7 （最短路径 2 ）。下一步骤是选择最小的边缘出射从超级节点。推理然后是一样的第一步：

One way to reason about what comes next is to pretend the algorithm merges "known" nodes into a single one. In the example, as soon as the shortest path to 2 is chosen, it merges 1 and 2 as a single logical node. All edges going out of 2 are increased by 7 (the shortest path to 2). The next step is to choose the smallest edge outgoing from the "supernode". The reasoning then is the same as the first step:

    6   _ 3
    |  /
  14| /9
    |/
   1,2-------4
        22  

在此状态下，下一个选择的边缘 1,2-3（9）。最短路径 3 设置为 9 和所有的边现在被认为是选择下一个最小（请注意如何的边缘 6 和 4 已更新）：

In this state, the next chosen edge is 1,2-3 (9). The shortest path to 3 is set as 9 and all of its edges are now considered to choose the next minimum (please note how the edges to 6 and 4 have been updated):

    6
    |
  11|
    |
   1,2,3----4
         20  

这篇关于Dijkstra算法背部追踪？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！