Правило для упрощения поиска.

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

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

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

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

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

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

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

Чтобы найти , достаточно найти минимальную временную метку всех соседей узлов и превратить эту метку в постоянную.

Теперь можно формально описать алгоритм и применить его к численному примеру. Будем применять для обозначения временного кратчайшего расстояния и для обозначения истинного кратчайшего расстояния.