Найдем кратчайший путь из вершины 1 в вершину 7 (рис. 19).

Рис. 19

1. Пометим вершину 1 индексом λ₁ = 0.

2. Смежными с 1-й являются вершины 2 и 3. ξ₂ = 0 + 3 = 3. ξ₃ = 0 + 1 = 1. Величина ξ₃ минимальна. Помечаем вершину 3: λ₃ = 1. Помечены вершины 1 и 3.

1. Смежными с помеченными вершинами (1 и 3) являются вершины 2, 4 и 5. ξ₂ = 0 + 3 = 3. ξ₄ = 1 + 1 = 2. ξ₅ = 1 + 6 = 7. Величина ξ₄ минимальна. Помечаем вершину 4 индексом λ₄ = 2. Помечены вершины 1, 3 и 4.

2. Смежными с помеченными вершинами (1, 3 и 4) являются вершины 2 и 5. ξ₅ = 2 + 4 = 6. ξ₅ = 1 + 6 = 7. ξ₂ = 0 + 3 = 3. ξ₂ = 2 + 2 = 4. Помечаем вершину 2: λ₂ = 3. Помечены вершины 1, 2, 3, 4.

3. Смежной с помеченными вершинами (1, 2, 3, 4) является вершина 5.

ξ₅ = 2 + 4 = 6. ξ₅ = 1 + 6 = 7. Помечаем вершину 5 индексом λ₅ = 6. Помечены вершины 1, 2, 3, 4 и 5.

1. Смежными с помеченными вершинами (1, 2, 3, 4, 5) являются вершины 6 и 7. ξ₆ = 6 + 2 = 8. ξ₇ = 6 + 9 = 15. Величина ξ₆ минимальна для вершины 6. Помечаем вершину 6: λ₆ = 8.

2. Смежная с помеченными вершинами (1, 2, 3, 4, 5, 6) вершина 7.

ξ₇ = 6 + 9 = 15. ξ₇ = 8 + 1 = 9. Помечаем вершину 7 индексом λ₇ = 9.

1. Для вершины 6 смежной является вершина 7. ξ₇ = 8 + 1 = 9. Величина ξ₇ минимальна. Помечаем вершину 7 индексом λ₇ = 9.

С помощью алгоритма Дейкстра мы получили длину кратчайшего пути из вершины 1 в вершину 7, которая составит 9. Кратчайшим путем является путь 1 – 3 – 4 – 5 – 6 – 7 (рис. 20).

Рис. 20

Задания

Для орграфа дана матрица весов. В позиции ( i, j ) записана длина дуги из вершины i в вершину j (ноль означает, что пути из i в j не существует). Если согласно матрице путь i  j существует, то путь j  i не существует. Задание: найти кратчайший путь из вершины 1 в вершину 5.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

Алгоритм Флойда – Уоршалла

Описание алгоритма

Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в графе (орграфе). В отличие от алгоритма Дейкстра и алгоритма Беллмана – Форда находит кратчайшие пути сразу для всех пар вершин. Как и в алгоритме Беллмана – Форда, дуговые расстояния могут быть как положительными, так и отрицательными, но также не должно быть циклов отрицательной длины. Во всех трех алгоритмах решение находится методом итераций, но в каждом алгоритме итерируются разные величины. Если в алгоритме Беллмана – Форда итерируется число дуг в пути, в алгоритме Дейкстра – длина пути, то в алгоритме Флойда – Уоршалла итерируется множество вершин, которые допускается иметь в качестве промежуточных вершин на путях. Как и оба других алгоритма, алгоритм Флойда – Уоршалла начинает с расстояний одной дуги (то есть без промежуточных вершин), выбранных в качестве исходных оценок для длин кратчайших путей. Затем вычисляются кратчайшие пути с тем ограничением, что промежуточной вершиной может быть только вершина 1, затем с ограничением, что промежуточными вершинами могут быть только вершины 1 и 2 и т.д.

Этот алгоритм в его «чистом» варианте абсолютно не подходит для нахождения кратчайших путей вручную, так как он весьма трудоёмок (скажем, для графа 4×4 мы имеем уже 64 итерации). Поэтому следует понять, на каких итерациях матрица не меняется, и затем попросту исключить их из рассмотрения.

Пример

Рис. 21

Условно процедуру нахождения кратчайшего пути в орграфе (рис. 21) можно разбить на несколько шагов.

1. Инициализация. На данном этапе мы формируем матрицу C [1..p,1..p] и «предварительный вариант» матрицы H. Элемент матрицы C_ij равен длине дуги из вершины i в вершину j, а если такой дуги нет, то он равен бесконечности.

Соответствующие элементы матрицы H равны вершине, в которую проведена дуга, длина которой указана в матрице С:

; .

1. «Вычёркиваем» первый столбец и первую строку матрицы T. Затем ищем в данной строке и данном столбце и «вычёркиваем» соответственно столбец или строку, где была найдена. Видим, что остаётся два элемента: 5 и (рис. 22).

Рис. 22

1. Проверяем оставшиеся элементы t_ij на неравенство t_ij > t_1j + t_i1. Если оно выполняется, то записываем на место проверяемого элемента сумму t_1j + t_i1 и параллельно пишем в соответствующую ячейку матрицы H номер вершины из её первого столбца, а если нет, то оставляем элемент без изменений (рис. 23).

Рис. 23

1. Повторяем шаги 1 - 3 для второго столбца и второй строки, третьего столбца и третьей строки и т. д. до p-го столбца и p-й строки:

i	Исходные данные на i-ом шаге	Результат на i-ом шаге
2
3

i	Исходные данные на i-ом шаге	Результат на i-ом шаге
4	EMBED Visio.Drawing.6

1. Таким образом, на выходе мы получаем, как и указано в алгоритме, две матрицы:

и .

Каждый элемент t_ij матрицы T содержит длину кратчайшего пути из вершины i в вершину j, а каждый элемент h_ij матрицы H содержит номер первой вершины, проходимой нами при следовании по этому пути.

Задания

Для орграфа дана матрица весов. В позиции ( i, j ) записана длина дуги из вершины i в вершину j ( означает, что пути из i в j не существует). Задание: нарисовать изображение графа, составить матрицы кратчайших расстояний и маршрутов.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

Алгоритм Форда – Фалкерсона

Описание алгоритма

В этом разделе под сетью мы понимаем связный орграф D (V, E), у которого есть одна вершина s со степенью захода 0 (источник) и одна вершина t со степенью исхода 0 (сток). Дуги сети нагружены неотрицательными вещественными числами, то есть задана функция c: E→R. Если - дуга, то c (e) - пропускная способность дуги.

Разрез сети - это разбиение множества вершин V на два непересекающихся подмножества S и T таких, что , . Обозначим через Р ⁺ множество всех дуг от S к T (то есть начало дуги в S, а конец дуги в T), через Р ^– – множество всех дуг от T к S. Под разрезом также понимают и ; под ориентированным разрезом (орразрезом) – множество дуг Р ⁺. Сумма пропускных способностей всех дуг разреза (орразреза) называется пропускной способностью и обозначается соответственно С(Р), С(Р ⁺).

Функция  : E → R является потоком в сети, если выполнены условия:

1. для любой дуги ;

2. для любой вершины сумма потоков по дугам, входящим в u, равна сумме потоков по дугам, исходящим из u ( (е) - поток по дуге е).

Величиной потока назовем сумму потоков по дугам, исходящим из S, обозначим её через W (). Нетрудно показать, что сумма потоков по дугам, входящим в t, равна W (). Если – разрез, то справедливо равенство

W ( ) = Ф (Р ⁺) – Ф (Р ^– ),

где Ф (Р ⁺), Ф (Р ^– ) – суммы потоков по дугам, входящим в Р ⁺, Р ^– соответственно.

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

Теорема Форда - Фалкерсона: пропускная способность сети равна пропускной способности минимального орразреза.

Поскольку доказательство теоремы носит конструктивный характер и используется при построении алгоритма, то кратко изложим его суть.

Соединим s с вершиной u при помощи цепи < s, u >, не учитывая направления дуг. Цепь < s, u > называется аугментальной, если дуги е⁺, направленные против движения, имеют положительный поток; иными словами, все величины с (е⁺) –  (е⁺),  (е ^–) строго положительны. Пусть t достижима из s при помощи такой цепи, тогда величину потока можно увеличить. Обозначим через K минимальное среди всех значений с (е⁺) –  (е⁺),  (е ^–); K > 0.