3. Алгоритм нахождения максимального пути

.

Для нахождения максимального пути граф G (сеть) должен быть ациклическим, ибо в противном случае может оказаться, что длины некоторых путей не ограничены сверху. Если G_n – ациклический граф, то для любых двух его вершин выполняется одно из трёх условий:

1. х_i предшествует х_j,

2. х_i следует за х_j,

3. нет пути между х_i и х_j.

1-ое и 2-ое условия одновременно не выполнимы из-за требуемой ацикличности графа.

Перед вычислением максимального пути в орграфе необходимо упорядочить вершины графа по алгоритму Фалкерсона. Сам алгоритм вычисления максимального пути чисто перечислительный. Он перебирает все возможные пути от текущей вершины до всех последующих, достижимых из текущей вершины.

Пусть d_j – длина максимального пути от вершины х₁ до вершины х_j, тогда удовлетворяет следующим рекуррентным соотношениям:

(*)

Соотношения (*) позволяют легко вычислить длины максимальных путей от S = х₁ до вершин, достижимых из вершины S. Сами пути могут быть построены методом последовательного возвращения (2-ой этап в алгоритме Дейкстры).

Пример. Граф (сеть, рис. 34) задан весовой матрицей Ω:

Рис. 36

Найти длину максимального пути из вершины х₁ в х₆ и сам этот путь.

Решение. Этот граф ациклический, поэтому возможно упорядочение его вершин по алгоритму Фалкерсона. Сделаем это графическим способом, переобозначив 2 вершины: х₄ назовём , а и применим рекуррентные формулы (*).

Р ис. 37

Этап 1.

Итак, длина максимального пути из х₁ в х₆ равна 30.

Этап 2.

- включаем дугу (x₅, x₆) в максимальный путь,

- включаем дугу ( , x₅) в максимальный путь,

- включаем дугу ( , ) в максимальный путь,

- включаем дугу (x₂, ) в максимальный путь,

- включаем дугу (x₁, x₂) в максимальный путь.

Итак, искомый путь таков: (x₁,x₂)- (x₂, ) - ( , )-

- ( ,x₅) - (x₅,x₆) или в первоначальных обозначениях

(x₁, x₂) - (x₂, x₄) - (x₄, x₃) - (x₃, x₅) - (x₅, x₆).

4. Особенности алгоритмов теории графов

1. Каждый алгоритм состоит из совокупности конечного числа правил и предписаний. Действия над графами (матрицей), производимые в соответствии с правилами, должны быть достаточно просты.

2. Алгоритм применяется в дискретном времени, правила алгоритма – по шагам, число шагов конечно.

3. Какое из правил будет применено на данном шаге или какое действие будет совершено в соответствии с некоторым правилом, зависит только от результатов предыдущих шагов.

4. Алгоритмы обладают свойством локальности: действие в соответствии с правилами или установление непротиворечивости некоторого действия правилам алгоритма происходит на основе анализа дуг, инцидентных данной вершине, или вершин, смежных с данной.

5. Алгоритмы обладают свойством массовости: применяются либо для всех, либо для некоторого бесконечного множества графов.

Вопросы для повторения.

1. Нахождение кратчайших путей с помощью алгоритма Дейкстры.

2. Нахождение кратчайших путей с помощью алгоритма Беллмана-Мура.

3. Алгоритм нахождения максимального пути.

4. Особенности алгоритмов теории графов.