Алгоритм Дейкстры нахождения кратчайшего маршрута от заданной вершины на графе транспортной схемы Заданной вершине xi начала маршрута присвоить постоянную метку [0

Алгоритм Дейкстры нахождения кратчайшего маршрута
от заданной вершины на графе транспортной схемы

Заданной вершине xi начала маршрута присвоить постоянную метку [0; –], где «0» означает, что кратчайшая длина маршрута от вершины xi до вершины начала равна Fi = 0, так как в данном случае вершина xi и есть вершина начала маршрута; знак «–» означает, что для исходной вершины исключается из рассмотрения возможность вернуться в эту вершину из любой предшествующей ей смежной вершины, так как, естественно, что входящая в кратчайший маршрут вершина транспортной схемы не может встретиться в нем более одного раза.
Определить все вершины xj, достижимые из смежной им вершины xi – последней из вершин графа, которым присвоена постоянная метка.
Установленным вершинам xj, не имеющим постоянных меток, присвоить временные метки (Fj = Fi + сij; i), где сij – вес ребра/дуги между хi и соответствующей xj, равный расстоянию между соответствующими пунктами. Если вершина xj уже имеет временную метку (Fj; k), полученную ранее от другой вершины хk, и если Fi + сij < Fj, то метка (Fj; k) заменяется на (Fj = Fi + сij; i).
Среди вершин, имеющих временные метки, выбрать вершину, в метке которой (Fs; q) значение расстояния Fs является наименьшим (если таких меток несколько, то выбирается любая их них). Положить q = i, метке данной вершины хi придать статус постоянной, и процесс определения искомого маршрута продолжить, вернувшись к пункту 2 алгоритма. Если все вершины графа получили постоянные метки, то процесс определения минимальных расстояний вершин графа до вершины начала маршрута завершен.
По заданной конечной вершине маршрута и имеющимся меткам вершин определить последовательность вершин соответствующего кратчайшего маршрута и его длину.

Читайте также:  Строка Вариант 2Отскок Hi Прочн МПа Отскок Hi Прочн МПа1 35

Вершине S начала маршрута присваиваем постоянную метку [0; –].
Для S смежные достижимые вершины без постоянных меток: a, b, c. Определяем временные метки этих вершин:
Вершина Метка Статус метки
S [0; –] постоянная
a (0 + 4; S) = (4; S) временная
b (0 + 5; S) = (5; S) временная
c (0 + 2; S) = (2; S) → [2; S] временная → постоянная
Поскольку наименьшее расстояние от начала маршрута среди временных меток имеет вершина c, то метке этой вершины придаем статус постоянной.
Для вершины c, последней с присвоенной постоянной меткой, смежные достижимые вершины: b, e. Определяем временные метки этих вершин:
Вершина Метка Статус метки
S [0; –] постоянная
a (4; S) временная
b (5; S), (2+1; c) = (3; c) → [3; c] временная → постоянная
c [2; S] постоянная
e (2+5; c) = (7; c) временная

Поскольку наименьшее расстояние от начала маршрута среди временных меток имеет вершина b, то метке этой вершины придаем статус постоянной.
Для вершины b, последней с присвоенной постоянной меткой, смежные достижимые вершины без постоянных меток: a, k. Определяем временные метки этих вершин:
Вершина Метка Статус метки
S [0; –] постоянная
a (4; S), (3+2; b) = (4; S) → [4; S] временная → постоянная
b [3; c] постоянная
c [2; S] постоянная
e (7; c) временная
k (3+6; b) = (9; b) временная
Для вершины a, последней с присвоенной постоянной меткой, смежные достижимые вершины без постоянных меток: e, k. Определяем временные метки этих вершин:
Вершина Метка Статус метки
S [0; –] постоянная
a [4; S] постоянная
b [3; c] постоянная
c [2; S] постоянная
e (7; c), (4+7; a) = (7; c) → [7; c] временная → постоянная
k (9; b), (4+5; a) = (9; a, b) временная
Для вершины e, последней с присвоенной постоянной меткой, смежные достижимые вершины без постоянных меток: t. Определяем временные метки этих вершин:
Вершина Метка Статус метки
S [0; –] постоянная
a [4; S] постоянная
b [3; c] постоянная
c [2; S] постоянная
e [7; c] постоянная
k (9; a, b) → [9; a, b] временная → постоянная
t (7+4; c) = (11; c) временная
Для вершины k, последней с присвоенной постоянной меткой, смежные достижимые вершины без постоянных меток: t. Определяем временные метки этих вершин:
Вершина Метка Статус метки
S [0; –] постоянная
a [4; S] постоянная
b [3; c] постоянная
c [2; S] постоянная
e [7; c] постоянная
k [9; a, b] постоянная
t (11; c), (9+5; k) → [11; c] временная → постоянная
Поскольку все вершины получили постоянные метки, заканчиваем процесс определения минимальных расстояний от начала маршрута.
Кратчайшие маршруты из S до любой другой вершины определяются от конечного пункта маршрута путем нахождения вершин согласно обратному порядку присвоения вершинам постоянных меток. Обратной последовательностью вершин от t в S является:
t [11; c] →c [2; S] → S
Следовательно, кратчайший маршрут из S в t определяется последовательностью вершин S → c → t; общая длина маршрута F*min = 11.

Читайте также:  Семена пшеницы содержат 0,2% сорняков. Найти вероятность того, что в 1000 семян будет 6 семян сорняков

Решение:

кратчайший маршрут из S в t: S → c → t; F*min = 11
Теорема Форда-Фалкерсона: на любой сети максимальная величина потока равна минимальной пропускной способности разреза.
Алгоритм решения задачи о максимальном потоке.

Построить начальный поток Х = (чем больше величина выбранного потока, тем быстрее решается задача).
На основе

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...