ウィキペディアでDijkstraのアルゴリズムの実装についての質問

Question

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の最短経路についてWikipediaで言及されています。私がここで理解できないことは、すべての頂点までの距離を無限大[行番号3]に設定している間に、行9ではu := vertex in Q with smallest dist[]を割り当てているが、すべての距離は無限大である（行番号3 ）どのように最小距離がありますか？

Answer 1

6行目には、距離の1つを無限大にしてくれるdist[source] := 0と記載されています。それが削除されると、ループの連続反復がdist[v] := altに設定され、より無限の距離が増えます。

Answer 2

Dijkstraのアルゴリズムの背後にあるアイデアは、最初はグラフ内のどのノードまでの距離も知らないので、それらをすべて無限に設定するということです。しかしながら、アルゴリズムが進行するにつれて、ノードの開始ノードから距離の推定値がある一種の「ボール」が成長する。最初は、距離をまったく移動していない状態で自ら到達可能であるため、開始ノードの推定距離を0に設定します。これは、アルゴリズムが明確に定義されている理由です。まず、距離を知っているノードがあります。ノードにアクセスしてノードを拡大すると、エッジの影響を考慮して、そのノードを離れる。

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

もう1つの重要な詳細は、距離が同じ場合、そのネクタイを任意に破ることができるということです。この場合、Dijkstraのアルゴリズムはうまく動作します。このアイデアに本当に反対する場合は、エッジコストのすべてに非常に小さな数値を追加することによって、人為的にすべての関係を破ることができます。

Answer 3

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