1 
function Dijkstra(Graph, source):
    for each vertex v in Graph:            // Initializations
        dist[v] := infinity ;              // Unknown distance function from source to v
        previous[v] := undefined ;         // Previous node in optimal path from source
    end for ;
    dist[source] := 0 ;                    // Distance from source to source
    Q := the set of all nodes in Graph ;
    // All nodes in the graph are unoptimized - thus are in Q
    while Q is not empty:                  // The main loop
        u := vertex in Q with smallest dist[] ;
        if dist[u] = infinity:
            break ;                        // all remaining vertices are inaccessible from source
        fi ;
        remove u from Q ;
        for each neighbor v of u:          // where v has not yet been removed from Q.
            alt := dist[u] + dist_between(u, v) ;
            if alt < dist[v]:              // Relax (u,v,a)
                dist[v] := alt ;
                previous[v] := u ;
            fi ;
        end for ;
    end while ;
    return dist[] ;
end Dijkstra.

上述算法已在 Wikipedia 中提到了 Dijkstra 最短路径。我在这里无法理解的是，虽然我们将所有顶点的距离设置为无穷大[第 3 行]，但在第 9 行我们正在分配u := vertex in Q with smallest dist[]，但由于所有距离都是无限的（如第 3 行中设置的那样）怎么可能有最小的距离？

4

3 回答 3

2

在第 6 行中，它说dist[source] := 0这使得距离之一是非无限的。一旦删除，循环集的连续迭代dist[v] := alt，创建更多的非无限距离。

于 2011-02-09T06:55:09.687 回答
1

在第 6 行中，到起始节点的距离设置为零。一切都从那里开始。

于 2011-02-09T06:53:51.147 回答
0

Dijkstra 算法背后的想法是，最初，您不知道到图中任何节点的距离，因此您将它们全部设置为无穷大。然而，随着算法的进行，它会从存在距离估计的节点的起始节点向外增长一种“球”。最初，您将起始节点与其自身的估计距离设置为 0，因为在完全不移动任何距离后，它从自身很容易到达。这就是为什么该算法定义明确的原因 - 最初，您有一些您知道距离的节点，并且每当您访问一个节点并扩展它时，您会通过考虑边缘的影响来减少与该节点所有邻居的距离离开那个节点。

不过，有趣的是，在某些情况下，您最终可能会发现其中一些距离是无穷大的。值得注意的是，如果某个节点 v 从起始节点无法到达，那么它的距离永远不会减少，并且 Dijkstra 的算法将在距源节点无限远的地方报告它。

另一个重要的细节是，如果在距离上出现平局，您可以任意打破平局。Dijkstra 的算法在这种情况下工作得很好。如果你真的反对这个想法，你可以通过在所有边缘成本上添加一个非常小的数字来人为地打破所有的联系。

于 2011-02-09T06:52:21.660 回答