Вопрос о реализации алгоритма Дейкстры в Википедии

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. 

приведенный выше алгоритм упоминается в Википедии для кратчайшего пути Дейкстры. Здесь я не могу понять, что, хотя мы установили расстояния до всех вершин как бесконечность [строка номер 3], в строке 9 мы назначаем u := vertex in Q with smallest dist[], но поскольку все расстояния бесконечны (как указано в строке 3) как может быть минимальное расстояние?

Answer 1

В строке 6 указывается dist[source] := 0, которая делает одно из расстояний бесконечным. После удаления последовательных итераций цикла установите dist[v] := alt, создавая больше не бесконечных расстояний.

Answer 2

Идея алгоритма Дейкстры заключается в том, что изначально вы не знаете расстояния до любого из узлов на графике, поэтому вы устанавливаете их все на бесконечность. Однако по мере того как алгоритм продолжается, он растет своего рода «шарик» наружу от начального узла узлов, где есть оценка расстояния. Первоначально вы устанавливаете расчетное расстояние стартового узла от себя до 0, так как оно тривиально доступно от самого себя, вообще не путешествуя. Вот почему алгоритм хорошо определен - изначально у вас есть узел, которому вы знаете расстояние, и всякий раз, когда вы посещаете узел и расширяете его, вы уменьшаете расстояние до всех соседей этого узла, рассматривая эффекты ребер оставляя этот узел.

Интересно, однако, есть случай, когда вы могли в конечном итоге с некоторыми из тех расстояний, которые были бесконечными. Примечательно, что если некоторый узел v не доступен из начального узла, то его расстояние никогда не уменьшается, и алгоритм Дейкстры сообщает об этом на бесконечности расстояния от исходного узла.

Еще одна важная деталь заключается в том, что в случае галстука на расстояниях вы можете разбить эту связь произвольно. В этом случае алгоритм Дейкстры отлично работает. Если вы действительно возражаете против этой идеи, вы можете искусственно разорвать все связи, добавив очень небольшое количество всех издержек.

Answer 3

В строке 6 расстояние до начального узла установлено на ноль. Все исходит оттуда.