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.

上記のアルゴリズムは、ウィキペディアの Dijkstra Shortest Path で言及されています。ここで理解できないのは、すべての頂点への距離を無限大に設定している間[行番号3]、9行目で割り当てu := vertex in Q with smallest dist[]ていますが、すべての距離が無限であるため(行番号3で設定されているように)どのようにして最小の距離がありえますか?

4

3 に答える 3

2

6行dist[source] := 0目では、距離の1つを非無限にするものを指定しています。それが削除されると、ループセットの連続した反復により、dist[v] := altより多くの非無限距離が作成されます。

于 2011-02-09T06:55:09.687 に答える
1

6 行目では、開始ノードまでの距離がゼロに設定されています。すべてはそこから始まります。

于 2011-02-09T06:53:51.147 に答える
0

ダイクストラのアルゴリズムの背後にある考え方は、最初はグラフ内のどのノードまでの距離もわからないため、すべてのノードを無限に設定するというものです。ただし、アルゴリズムが進行するにつれて、距離の推定値があるノードの開始ノードから外側に向かって一種の「ボール」が成長します。最初に、開始ノードからそれ自体までの推定距離を 0 に設定します。これは、距離をまったく移動しないと自明に到達できるためです。これが、アルゴリズムが明確に定義されている理由です。最初は、距離がわかっているノードがあり、ノードにアクセスして展開するたびに、エッジの影響を考慮して、そのノードのすべての隣接ノードまでの距離を減らします。そのノードを離れます。

しかし興味深いことに、これらの距離の一部が無限大になる場合があります。特に、一部のノード v が開始ノードから到達できない場合、その距離は減少せず、ダイクストラのアルゴリズムはソース ノードから無限遠にあると報告します。

もう1つの重要な詳細は、距離が同点の場合、その同点を任意に破ることができるということです. その場合、ダイクストラのアルゴリズムは問題なく機能します。この考えに本当に反対している場合は、すべてのエッジ コストに非常に小さな数を追加することで、人為的にすべての関係を断ち切ることができます。

于 2011-02-09T06:52:21.660 に答える