Презентация на тему Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах

взвешенном ориентированном графе G(X,U) требуется определить кратчайший путь из

i-й вершины в j-ю.

1

2

3

4

1

2

3

4

2 7

5 3

1

Граф G(X,U) Кратчайший путь из 1-й вершины в 3-ю

1

2

3

из s-й вершины в t-ю

P(s)=0.
Шаг 2. Всем вершинам множества Х\ присвоить

потенциал, равный ∞.
Шаг 3. Каждой q-й вершине множества Х\
присваивается потенциал P(q):


Шаг 4. Если потенциал хотя бы одной вершины
изменился, то перейти к шагу 3, в противном
случае – к шагу 5.
Шаг 5. Конец алгоритма. Потенциал t-й вершины равен
кратчайшему пути в нее из вершины .

в 4-ю.






1
2
3
4
5
6

2 5

9 3

4 6

1


2

0

∞



∞

∞



∞

∞

2 5

2 5

1


2

11


2

1


2

4 6

4 6

9 3

9 3

∞


4

15

1
0

1
0

2

2

2

3

4

3

4

4

5

6

15

5

6

11


2

7


4

1
0

2 5

2 6

3 5

4

8


2

7


4

12

4 6

9 3

1



2

а) б) в) г)
Порядок расстановки потенциалов на каждой итерации – по часовой стрелке.

из выбранной вершины во все остальные.
Исключается необходимость перебора всех

путей.
Высокое быстродействие.
Легкая программная реализация.
Универсальность: метод применим к ориентированным и неориентированным графам.
Недостатки:
Вес каждой дуги должен быть положительным.

вершины во все остальные.

1






3

7
8

10


6

8
2




9


11

7
4

12




1

7

6

5

4

3

2

максимальный однородный поток на графе G(X,U) из вершины s

в вершину t, если поток по каждой дуге графа (i,j) не может превышать ее пропускной способности r(i,j)

– поток по дуге

,
r(i,j) – пропускная способность дуги ;
- вершина – источник;
- вершина – сток.

Задача линейного программирования

в которой:
эмиссионная способность источника ограничена;
поглощающая способность стока ограничена;
на

графе имеется несколько источников и стоков.

1. Полученный граф G(X,U’) заменяется на G’(X,U’) такой, что:

Шаг 2. Методом потенциалов ищется кратчайший путь L из
Шаг 3. Если длина такого пути равна ∞, то перейти к шагу 9, в противном случае – к шагу 4.
Шаг 4. На графе G(X,U) выбирается дуга (p,q), принадлежащая L, для которой справедливо:

На графе G(X,U) вес всех дуг, принадлежавших пути L,

изменяется следующим образом:

Шаг 6. Образовавшиеся дуги с нулевым весом
на G(X,U) отбрасываются.
Шаг 7. Вес r(p,q) добавить к ранее накопленной сумме S.
Шаг 8. Перейти к шагу 1.
Шаг 9. Конец алгоритма. Суммарный вес дуг, найденных на шаге 4 каждой итерации, равен максимальному потоку из источника в сток.

a) b) S=5. c) L=∞.

1

S

S

S

S

t

t

t

t

2

1 2

1 2

1 2

1 4 1 0,25 1 1

2 4 0,5 0,25 2 0,5

1 1

1 1

S

t

1

2

1




1

алгоритма.

1

1
1 1 2 1



1 1

1

Максимальный поток F из 1-й вершины в 6-ю равен двум, но вышеприведенный алгоритм покажет F = 1 (на графе этот поток выделен красным цветом).

потока.
2. Определить максимальный поток из источника в сток на

графе G(X,U):

1 2 3 8

4 5

6 7

2
3

5

4

3

5

8

6
1

7


3



9

графе G(X, U) называется подмножество дуг, удаление которых разрывает

все пути из источника в сток.
2. Минимальным разрезом на взвешенном ориентированном графе G(X, U) называется разрез, суммарный вес дуг которого минимален.




Варианты разрезов вверху выделены красным цветом

если дуга (i,j) принадлежит минимальному разрезу и равная нулю

в противном случае.
- множество дуг, принадлежащих d-у пути, ведущему из вершины-источника в вершину-сток .

7

5

9 3

равна величине максимального потока.