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

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

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

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