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

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

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

Answer 3

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

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

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