Задача о кратчайшем пути

 

Необходимо найти кратчайший путь между пунктами 0 и 8.

 

 

7 11

 

6 10 9

 

7 9

11 5 3

 

 

12 13

 

X₀ = 0

X₁ = +¥ = 3

X₂ = +¥ = 6

X₃ = +¥ = 12

X₄ = +¥ = 13

6 + 7

3 + 11

X₅ = +¥ = 15

3 + 12

X₆ = +¥ = 16

7 + 12

6 + 10

X₇ = +¥ = 18

13 + 5

X₈ = +¥ = 21

12 + 11

16 + 9

13 + 9

13 + 5 + 3

15 + 13

 

Таким образом, кратчайшее расстояние между двумя пунктами 0 и 8 = 6 + 7 + 5 + 3 = 21

 

 

Задача о максимальном потоке в сети

 

 

Постановка задачи

 

Рассмотреть задачу о максимальном потоке в сети. Решить конкретную задачу на сети с 8-9 вершинами.

 

 

Исходные данные

 

Определить максимальный поток в сети, изображенной на Рисунке 6 из вершины x₀ в вершину x₈, где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях.

Рисунок 6

 

 

Решение

 

Составим матрицу пропускных способностей дуг данной сети и представим сеть в матричной форме (см. Таблицу 1).

 

Таблица 1

x0xj xi	x1	x2	x3	x4	x5	x6	x7
x0			2-
x1
x2
x3+							6-
x4
x5
x6
x7			+

 

В качестве начального возьмем нулевой поток z⁰_ij = 0. Найдем какой-нибудь путь, идущий из x₀ в x₇ по ненасыщенным дугам. Для этого в нулевой строке таблицы выберем какой-нибудь элемент c_ij, отличный от нуля, например c₀₃. Из вершины x₀ можно перейти в x₃. Для наглядности дугу (x₀, x₃) проведем прямо в нулевой строке таблицы из нулевого столбца в 3-й. Теперь мы находимся в вершине x₃. Чтобы зафиксировать это, сместимся по пятому столбцу до строки с тем же 3-м номером. В 3-й строке имеется 3 ненулевых элемента соответственно в 4-м, 5-м и 7-м столбцах. Это означает, что из x₃ можно перейти или в x₄, в x₅ или в x₇. Пойдем в сток x₇. Этот переход изображен стрелкой в 3-й строке с началом в 3-м столбце и концом в 7-м. Таким образом, по таблице пропускных способностей дуг сети мы нашли путь, ведущий по ненасыщенным дугам из источника в сток:

 

m₁ = [x₀, x₃, x₇].

 

Теперь по таблице надо узнать пропускную способность q₁ найденного пути и уменьшить пропускные способности всех дуг этого пути на q₁, а симметричных им дуг – увеличить на q₁. Для этого отмечаем знаком «-» числа в тех клетках, где находятся концы дуг, а числа в клетках, симметричных указанным относительно главной диагонали, отмечаем знаком «+». Пропускная способность найденного пути, очевидно, равна наименьшему среди чисел, отмеченных знаком «-» (Таблица 1).

 

q₁ = 2

 

Из всех чисел, отмеченных знаком «-», вычитаем наименьшую пропускную способность q₁. Получаем Таблицу 2. Это – сеть с измененными пропускными способностями дуг.

 

Таблица 2

x0xj xi	x1	x2	x3	x4	x5	x6	x7
x0		4-
x1
x2+				3-
x32
x4		2+					5-
x5
x6
x7				5+

 

Ищем новый путь, идущий из источника в сток по ненасыщенным дугам и процедуру повторяем. Получаем путь m₂ и пропускную способность q₂:

 

m₂ = [x₀, x₂, x₄, x₇]

q₂ = 3

 

Далее

 

Таблица 3

x0xj xi	x1	x2	x3	x4	x5	x6	x7
x0	2-
x1+					5-
x23
x32
x4
x5	4+					3-
x6					2+		8-
x7						2+

 

m₃ = [x₀, x₁, x₅, x₆, x₇]

q₃ = 2

 

Таблица 4

x0xj xi	x1	x2	x3	x4	x5	x6	x7
x0
x12
x23
x32
x4
x5
x6
x7

 

Из Таблицы 4 видно, что не существует ни одного пути из источника в сток. (Из x₀ можно перейти только в x₂, а оттуда – обратно в x₀). Следовательно, увеличить поток нельзя.

 

Для определения величины полученного максимального потока вычитаем из элементов Таблицы 1 соответствующие элементы Таблицы 4. Записывая только положительные из найденных разностей, получаем Таблицу 5, указывающую максимальный поток в заданной сети с величиной

 

w* = z₃₇ + z₄₇ + z₆₇ = q₁ + q₂ + q₃ = 7

 

Таблица 5

x0xj xi	x1	x2	x3	x4	x5	x6	x7
x0
x1
x2
x3
x4
x5
x6
x7