Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Дейкстры
В процессе выполнения этого алгоритма при переходе от узла к следующему узлу используется специальная процедура пометки ребер. Обозначим через кратчайшее расстояние от исходного узла 1 до узла , через — длину ребра . Тогда для узла определим метку следующим образом:
, .
Метки узлов в алгоритме Дейкстры могут быть двух типов: временные и постоянные. Временная метка впоследствии может быть заменена на другую временную, если будет найден более короткий путь к данному узлу. Когда же станет очевидным, что не существует более короткого пути от исходного узла к данному, статус временной метки изменяется на постоянный.
Вычислительная схема алгоритма состоит из следующих шагов. Шаг 0. Исходному узлу (узел 1) присваивается метка . Полагаем . Шаг 1. a) Вычисляются временные метки для всех узлов , которые можно достичь непосредственно из узла и которые не имеют постоянных меток. Если узел уже имеет метку , полученную от другого узла , и если тогда метка заменяется на . b) Если все узлы имеют постоянные метки, процесс вычислений заканчивается. В противном случае выбирается метка с наименьшим значением расстояния среди всех временных меток (если таких меток несколько, то выбор произволен). Полагаем и повторяем шаг .
|