Шаг 2. Множество вершин непосредственно следующих за с временными метками . Пересчитываем временные метки этих вершин:
;
;
.
Шаг 3. Одна из временных меток превращается в постоянную:
Следовательно, .
Шаг 4. , происходит возвращение на второй шаг.
Шаг 2. Множество вершин непосредственно следующих за с временными метками . Пересчитываем временные метки этих вершин:
;
Шаг 3. Одна из временных меток превращается в постоянную:
Следовательно, .
Шаг 4. , происходит возвращение на второй шаг.
Четвёртая итерация.
Шаг 2. Множество вершин непосредственно следующих за с временными метками . Пересчитываем временные метки этих вершин:
;
Шаг 3. Одна из временных меток превращается в постоянную:
Следовательно, .
Шаг 4. , происходит возвращение на второй шаг.
Шаг 2. Множество вершин непосредственно следующих за с временными метками . Пересчитываем временные метки этих вершин:
;
Шаг 3. Одна из временных меток превращается в постоянную:
Следовательно, .
Шаг 4. , конец первого этапа.
Шаг 5. Составим множество вершин непосредственно предшествующих вершине с постоянными метками . Проверим для этой вершины выполнение
;
.
Включаем дугу в искомый путь и полагаем .
Шаг 6. , следовательно. возвращаемся к пятому шагу.
Шаг 5. Составим множество вершин непосредственно предшествующих вершине с постоянными метками . Проверим для этой вершины выполнение
;
;
.
Включаем дугу в искомый путь и полагаем .
Шаг 6. , завершение второго этапа.
Кратчайший путь образует последовательность дуг .
Для нахождения максимального пути граф G (сети) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху. Если G – ациклический граф, то для любых двух его вершин выполняется одно из трёх условий:
1. предшествует , .
2. следует за , .
3. Нет пути между и .
Из-за требуемой ацикличности графа первое и второе условия одновременно не выполнимы.
Перед вычислением максимального пути в орграфе необходимо упорядочить вершины графа по алгоритму Фалкерсона. Сам алгоритм вычисления максимального пути чисто перечислительный. Он перебирает все возможные пути от текущей вершины до всех последующих, достижимых из текущей вершины.
Пусть ‑ длина максимального пути от вершины до вершины , тогда величина удовлетворяет следующим рекуррентным соотношениям:
(1)
Соотношения (1) позволяют легко вычислить длины максимальных путей от до вершин, достижимых из вершины s. Сами пути могут быть построены методом последовательного возвращения (второй этап в алгоритме Дейкстры).
Пример. Граф G задан матрицей весов Ω. Найти длину максимального пути из вершины в и сам этот путь.
По данной матрице весов построен граф на рис.15. Этот граф ациклический, поэтому возможно упорядочение его вершин по алгоритму Фалкерсона. Сделаем это графическим способом.
Рис. 15
Графический способ упорядочивания вершин графа (алгоритм Фалкерсона)
1. Вершина -не содержит входящих дуг, следовательно, отнесём её к первойгруппе.
2. Вычёркиваем вершину и все дуги, исходящие из . Получим граф на рис.16.
Рис. 16
В полученном графе опять находим вершины, в которые не заходит ни одна дуга. Это вершина . Отнесём её ко второй группе.
3. Вычёркиваем вершину и все дуги, исходящие из . Получим граф на рис.17.
Рис. 17
В полученном графе опять находим вершины, в которые не заходит ни одна дуга. Это вершина . Отнесём её к третьей группе.
4. Вычёркиваем вершину и все дуги, исходящие из . Получим граф на рис.18.
Рис. 18
Рис. 19
В полученном графе опять находим вершины, в которые не заходит ни одна дуга. Это вершина . Отнесём её к четвёртой группе.
5. Вычёркиваем вершину и все дуги, исходящие из . Получим граф на рис.19.
Рис. 20
Находим вершины, в которые не заходит ни одна дуга. Это вершина . Отнесём её к пятой группе.
6. Вычёркиваем вершину и все дуги, исходящие из . Получим граф на рис.20.
Находим вершины, в которые не заходит ни одна дуга. Это вершина . Отнесём её к шестой группе
Изоморфный граф с упорядоченными вершинами представлен на рис.21.
