Оптимизация пути в графах с контурами.

Для графов с контурами поиск максимального пути затруднён, т.к. он может не существовать. Для отыскания минимального пути существуют разные алгоритмы.

Алгоритм Форда.

Общая постановка задачи:

Задан произвольный связный орграф, каждой дуге которого приписано положительное число. Найти минимальный путь между двумя вершинами графа.

Примечание: Порядковая функция графа не задана.

Решение: Для поиска минимального пути между x₀ и x_n руководствуются следующими правилами:

1. Вершине x₀ приписывается метка ₀=0. Всем остальным x_i приписывается _i=.

2. Выбирается произвольная дуга x₀x_i и вершине x_i приписывается метка _i=₀+l(x₀,x_i), где l(x₀,x_j) - вес дуги между x₀ и x_i.

3. Для вершины x_j с меткой _j ищется вершина x_i, от которой идёт такая дуга в x_j, что _j_j и где: _j=_i+l(x_i,x_j).

Вершине x_j приписывается метка _j.

4. После разметки всех вершин графа для произвольной вершины x_j с меткой _j рассматриваем все вершины x_i с дугами, ведущими в вершину x_j , и выбирается новая метка _j_j и такая, что _j является минимальной из всех возможных меток.

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

6. Выбор минимального пути осуществляют по правилам получения минимального пути для графа без контуров.

Пример.

Найти минимальный путь из x₀ в x₆.

1 шаг. Вершине x₀ приписывается метка ₀=0. Всем остальным x_i приписывается _i=.

2 шаг. Рассматриваем вершину x₁ и дугу x₀x₁ . Вершине x₁ приписываем метку ₁=₀+l(x₀,x₁)=0+4=4.

3 шаг. Рассматриваем вершину x₃ и дугу x₀x₃ . Тогда ₃=₀+l(x₀,x₃)=0+2=2.

4 шаг. Рассматриваем вершину x₂ и дугу x₀x₂ . Тогда ₂=₀+l(x₀,x₂)=0+5=5.

5 шаг. Рассматриваем вершину x₅ и дугу x₀x₅ . Тогда ₅=₀+l(x₀,x₅)=0+4=4.

6 шаг. Рассматриваем вершину x₄ и дугу x₁x₄ . Тогда ₄=₁+l(x₁,x₄)=4+2=6.

7 шаг. Рассматриваем вершину x₆ и дугу x₄x₆ . Тогда ₆=₄+l(x₄,x₆)=6+1=7.

Разметка вершин показана на рисунке кружками. Выбор дуги (x_i,x_j) при разметке вершины x_j осуществляется совершенно произвольно. Единственное ограничение: метка _i вершины x_i не должна быть равна .

8 шаг. Рассматриваем вершину x₂ и стремимся уменьшить её метку. Для этого рассматриваем все дуги, ведущие в x₂: выписываем все возможные выражения для метки ₂: ₂=₀+l(x₀,x₂)=0+5=5.

₂=₃+l(x₃,x₂)=2+1=3.

₂=min=3, поэтому заменяем метку вершины x₂ на 3.

9 шаг. Аналогично для x₄ : ₄=₁+l(x₁,x₄)=4+2=6.

₄=₂+l(x₂,x₄)=3+2=5.

₄=min=5, поэтому заменяем метку вершины x₄ на 5.

10 шаг. Аналогично для x₅ : ₅=₃+l(x₃,x₅)=2+1=3.

₅=₄+l(x₄,x₅)=5+2=7.

₅=min=3, поэтому заменяем метку вершины x₅ на 3.

11 шаг. Аналогично для x₆ : ₆=₄+l(x₄,x₆)=5+1=6.

₆=₂+l(x₂,x₆)=3+3=6.

₆=₅+l(x₅,x₆)=3+5=8.

₆=min=6, поэтому заменяем метку вершины x₆ на 6.

12 шаг. Для x₁ понижение невозможно.

Дальнейшее понижение меток вершин невозможно, поэтому прекращаем разметку.

13 шаг. Ищем минимальный путь из x₆ в x₀ .

(x₆ , x₄ , x₂ , x₃ , x₀) длина пути: 2+1+2+1=6

(x₆ , x₂ , x₃ , x₀) длина пути: 3+2+1=6

Пример для самостоятельной работы: