Определение кратчайших путей в графе методом Дейкстры.

Алгоритм:

1.начальной вершине присваиваем вес равный 0, все остальным – равный ∞.

2.из полученных расстояний выбираем наименьшее (в качестве постоянного наименьшего расстояния) Вершина соответствующая этому расстоянию – «определенная»

3.определяем новые расстояния к вершинам смежным с определенными по выражению

L′(v)= min (L(v); L(u)+a(u, v)))

4.определенная вершина удаляется из списка вершин к которым еще не определено расстояние

5.повторяем пункт 2-4 до тех пор, пока не станут определены все вершины графа, либо заданная конечная вершина T.

30. Определение кратчайших путей в графе методом Флойда-Уоршолла.

Алгоритм:

1.S=0

2. ,

3. к=1

4.рассматриваем К-тый столбец матрицы и в множество Ai выписываем номера элементов столбца ≠0 и ∞

5.рассматриваем К-тую строку матрицы и в множество Aj выписываем номера элементов строки ≠0 и ∞ (имеется в виду 0 по главной диагонали)

6.составляем декартово произведение Ai*Aj

7. для пар полученных в декартовом произведении рассчитываются новые значения в множестве

8.если < , то вносятся изменения в матрицу путей =

9.значение счетчика S=S+1, w^(S+1), z^(S+1)

10.проверяется значение счетчика к, если к>h => k=k+1 и переход к пункту 4, иначе проверяется вносились ли изменения в матрицу w^(S), z^(s) во время изменения значения k от 1 до n. Если изменения не вносились, то конец алгоритма, иначе следовать к пункту 3.

31. Максимальный поток в сети. Основные понятия.

Поток определяет способ передачи некоторых объектов из 1 вершины графа в другую по его дугам (ориентированным ребрам). Вершина, из которой начинается перемещение – источник (S).

Вершина, в которой заканчивается перемещение – сток (t). Объекты перемещения из S в t называются единицами потока.

Количество единиц потока проходящих по дуге (x, y) называются потоком по дуге (f(x, y))

C(x, y) – пропускная способность дуги (max количество единиц, которое можно передать за единицу времени)

Поток из S в t называется стационарным, если его дуговые потоки остаются неизменными в каждую единицу времени.

Дивергенцией ф-ии f в x называется разность сумм ее значений на исходящих и входящих в вершину x дугах.

Разрезом графа называется такое разбиение множества вершиной графа В на 2 подмножества X и , такое что, X принадлежит S, а - t.

Разрез сети с наименьшей пропускной способностью называется min разрезом.

Max поток в сети не может превышать пропускную способность min разреза в сети.