Описание процесса поиска кратчайших путей от одного узла до всех остальных

1) Начиная поиск , приписываем каждому узлу длину дуги , т.е. временные метки узлов. Среди всех временных меток выбираем минимальную и превращаем ее в постоянную. Таким образом, становится помеченной постоянно (постоянная метка.

2) Чтобы найти , не нужно искать все пути из двух дуг, достаточно рассмотреть те из них, у которых первая дуга есть . В качестве временных меток приписываем узлам длины путей из одной дуги.

3) Далее сравниваем (длину одной дуги) с (длиной пути из двух дуг) и минимальное из этих двух значений приписать как временную метку вершине .

4) Минимум среди всех временных меток есть .

Постоянная метка указывает истинное кратчайшее расстояние от до . Временная метка узла указывает либо длину дуги , либо длину пути из в постоянный узел , дополненного дугой .