Описание алгоритма нахождения кратчайшего маршрутаАлгоритм представляет собой итерационную процедуру, в которой каждому узлу присваивается метка – либо постоянная и при этом показывающая расстояние от этого узла до выделенного, либо временная, где это расстояние оценивается сверху. В результате каждой итерации оценки уточняются, и ровно одна временная метка меняет свой статус на постоянную (после чего уже не меняется). Начнем с того, что пометим начальный узел и объявим эту метку постоянной. 1-шаг. Рассмотрим все дуги, исходящие из начального узла, и припишем всем узлам, которые эти дуги с ним соединяют, временные метки. Временная метка узла на 1-м шаге строится по следующему правилу: Это упорядоченная пара, первый элемент которой – начальный узел (уже имеющий постоянную метку), а второй элемент – число, равное длине дуги, соединяющей этот узел с начальным. Затем среди всех узлов с временными метками выбираем узел, расстояние которого от начального узла минимально. Если таких узлов несколько, выбираем любой. И объявляем временную метку выбранного узла постоянной. 2-шаг. Рассмотрим все дуги, исходящие из узлов с постоянными метками (теперь их уже два), и снабдим все узлы, в которые идут эти дуги, временными метками по следующему правилу: 1) Если новый узел не был помечен ранее, то временная метка – это упорядоченная пара, первый элемент которой – узел с постоянной меткой, из которого выходит выбранная дуга, а второй элемент – число, равное длине маршрута, ведущего в этот узел по узлам с постоянными метками, считая от начального узла. 2) Если узел уже имел временную метку, необходимо поступить так – сравнить длины старого и нового маршрутов, связывающих этот узел с начальным узлом, и либо заменить прежнюю временную метку на новую (если длина нового маршрута оказалась меньше длины старого), либо оставить ту же временную метку (если это не так). В результате мы получим новый набор узлов с временными метками. Выберем тот из узлов, длина маршрута до которого от начального узла является наименьшей. Если таких узлов несколько, выбираем любой и объявляем его временную метку постоянной. Последующие шаги проводятся по тому же правилу, что и 2-шаг, и заканчиваются присвоением постоянной метки очередному узлу сети. Так как на каждом шаге число узлов с постоянными метками увеличивается на единицу, то, сделав n – 1 шаг (считаем, что в сети n узлов), мы присвоим постоянные метки всем n узлам сети. По этим постоянным меткам кратчайшие маршруты, ведущие из начального узла в каждый из остальных узлов сети, легко восстанавливаются.
Задача №3. Найти максимальный поток по данному графу
|
