Читайте также:
|
Шаг 1. Присвоение вершинам начальных меток.
Полагаем 
и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин 
полагаем 
и считаем эти метки временными. Пусть 
, 
– обозначение текущей вершины.
Шаг 2. Изменение меток.
Для каждой вершины 
с временной меткой, непосредственно следующей за вершиной , меняем её метку в соответствии со следующим правилом:
.
Шаг 3. Превращение метки из временной в постоянную.
Из всех вершин с временными метками выбираем вершину 
с наименьшим значением метки:
.
Превращаем эту метку в постоянную и полагаем 
.
Шаг 4. Проверка на завершение первого этапа.
Если 
, то 
– длина кратчайшего пути от s к t. В противном случае происходит возвращение ко второму шагу.
Дата добавления: 2015-04-11; просмотров: 84 | Поможем написать вашу работу | Нарушение авторских прав |