Как работает алгоритм поиска кратчайшего пути между двумя вершинами в графе?

Алгоритм Дейкстры — алгоритм поиска кратчайшего пути между двумя вершинами в графе. 13 Он работает только для графов без рёбер отрицательного веса. 3

Принцип работы: 3

1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине — 0. 3
2. Все вершины не посещены. 3
3. Первая вершина объявляется текущей. 3
4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной. 3
5. Среди невыделенных вершин ищется вершина с минимальным весом. 3 Если такая не найдена, то есть вес всех вершин равен бесконечности, то маршрута не существует. 3 Следовательно, выход. 3 Иначе, текущей становится найденная вершина. 3 Она же выделяется. 3
6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины. 3
7. Переход на шаг 4. 3

Затем алгоритм использует эти метки, чтобы проследить обратный путь. 1