– Остальные вершины помечаются с бесконечными весами, за исключением начальной вершины у которой вес равен 0.
– Все вершины и их веса заносятся в приоритетную очередь (обычно в виде «кучи»).
Шаг 2: Обновление весов соседних вершин
– Извлекается вершина с наименьшим весом из приоритетной очереди.
– Рассматриваются все соседние вершины данной вершины.
– Если новая сумма веса текущей вершины и веса ребра до соседней вершины меньше, чем текущий вес соседней вершины, то обновляется вес соседней вершины.
Шаг 3: Повторение шага 2 до обработки всех вершин
– Процесс обновления весов соседних вершин повторяется до тех пор, пока все вершины не будут обработаны.
Шаг 4: Получение результата
– По завершении алгоритма Дейкстры, веса вершин будут содержать наименьшую сумму весов для каждой вершины относительно начальной вершины.
– Минимальное расстояние между начальной вершиной и конечной вершиной можно получить путем извлечения веса конечной вершины.
Применение алгоритма Дейкстры в формуле УКП позволяет эффективно находить минимальный путь между двумя вершинами, что играет важную роль в определении кратчайшего пути и вычислении значения элемента «минимальное расстояние между вершинами» (Md) в формуле УКП.