위키 백과에서 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 최단 경로에 대해 위키피디아에서 언급되었습니다. 여기서 내가 이해할 수없는 것은 모든 정점에 대한 거리를 무한대 [행 번호 3]로 설정하는 동안 9 행에서 u := vertex in Q with smallest dist[]을 할당하지만 모든 거리가 무한대이므로 (행 번호 3에 설정된대로)) 어떻게 가장 작은 거리가있을 수 있습니까?

Answer 1

라인 6에서는 거리 중 하나가 무한대가되도록 dist[source] := 0라고 말합니다. 루프가 제거되면 루프의 연속적인 반복이 dist[v] := alt으로 설정되어보다 무한 거리가 생성됩니다.

Answer 2

Dijkstra 알고리즘의 아이디어는 처음에는 그래프의 노드에 대한 거리를 모르기 때문에 모든 것을 무한대로 설정한다는 것입니다. 그러나 알고리즘이 진행됨에 따라 거리의 추정치가있는 노드의 시작 노드에서 바깥쪽으로 일종의 "공"이 생깁니다. 초기에는 거리가 전혀없는 상태에서 스스로 도달 할 수 있기 때문에 시작 노드의 예상 거리를 0으로 설정합니다. 이것이 알고리즘이 잘 정의 된 이유입니다 - 처음에는 거리를 알고있는 노드가 있고, 노드를 방문하여 확장 할 때마다 가장자리의 영향을 고려하여 해당 노드의 모든 이웃에 대한 거리를 줄입니다 그 노드를 떠난다.

흥미롭게도, 은 일 수 있으며 그 중 일부는 무한대 인 경우가 있습니다. 특히, 어떤 노드 v가 시작 노드로부터 도달 할 수 없다면, 그 거리는 결코 줄어들지 않으며, Dijkstra의 알고리즘은 소스 노드로부터 거리 무한대에 그것을보고 할 것이다.

또 다른 중요한 세부 사항은 거리가 동점 일 경우 임의로 해당 타이를 끊을 수 있다는 것입니다. Dijkstra의 알고리즘은이 경우 잘 작동합니다. 이 아이디어에 정말로 반대한다면 모든 가장자리 비용에 아주 작은 숫자를 추가하여 인위적으로 모든 관계를 해할 수 있습니다.

Answer 3

라인 6에서 시작 노드까지의 거리는 0으로 설정됩니다. 거기에서 모든 것이 진행됩니다.