Тема: Сетевые модели (стр. 3 )

Пример. Применим алгоритм построения увеличи­вающей цепи к графу, изображенному на рис. 1.15.

Для любой отмеченной вершины будем просматривать все инцидентные ей дуги. Отмечаем источник s. Дуги (s, p), (s, n) отмечаем как выходящие увеличивающие, а дугу (r, s) – как входящую уменьшающую (рис. 1.16).

В скобках указаны вершины, соединенные с новыми вершинами отмеченными дугами. Далее просматриваем дуги, инцидентные р (рис. 1.17). Дугу (p, r) не рассматриваем, поскольку вершина r уже отмечена. Далее, просматривая дуги, инцидентные n, отмечаем дугу (n, t) и вершину t
(рис. 1.18).

На этом просмотр заканчиваем, так как отмечен сток t. Идя в обратном направлении, получаем увеличиваю­щую цепь (s, n, t)

Алгоритм отыскания максимального по­тока в сети

Данный алгоритм, использующий увеличивающие цепи, называется алгоритмом Форда. Он состоит из следую­щих шагов.

1. Выбирают некоторый поток f(α) из s в t (напри­мер, f(α)=0)

2. Находят классы увеличивающих и уменьшаю­щих дуг.

Применяют алгоритм поиска увеличивающей цепи из s в t. Если такой цепи нет, то поток f – максималь­ный. Если цепь С найдена, то перейти к
шагу 4.

4. Находят .

5. Пусть δ > 0 наименьшее из этих чисел.

6. Увеличивают поток вдоль цепи С на δ и пере­ ходят к шагу 2.

Очевидно, что построенный таким образом поток удов­летворяет следующим условиям:

Этот поток является максимальным. Если начальные дан­ные целочисленны, то выполнение алгоритма Форда за­вершается за конечное число шагов.

Задача о кратчайшем пути между двумя вершинами графа

Алгоритм Дейкстры

Пусть каждой дуге (х, у) графа G поставлено в соот­ветствие число , которое называется длиной этой дуги (если вершины х и у не соединены дугой, то полагают . Длина пути определяется как сумма длин отдельных дуг, составляющих этот путь. Тре­буется найти кратчайший путь между двумя заданными вершинами s и t графа G.

Алгоритм поиска кратчайшего пути В ходе выполнения алгоритма окрашивают вершины и дуги графа и вычисляют величины d(x), равные крат­чайшему пути из вершины s в вершину х, включающему только окрашенные вершины.

1. Полагают для любого. Окрашивают вершину s и полагают .

2. Для каждой неокрашенной вершины х пересчиты­ вают величину по формуле .

Если для всех вершин, то вычисления заканчи­вают. В графе G отсутствуют дуги из вершины s в не­окрашенные вершины.

В противном случае окрасить вершину х, для кото­рой величина d(x) минимальна, и дугу, ведущую в вер­шину х. Полагают у=х.

3. Если y=t, то кратчайший путь найден. В против­ном случае переходят к шагу 2.

С помощью описанного алгоритма можно определить кратчайший путь из s во все вершины исходного графа. Для этого процедуру окрашивания нужно продолжить до тех пор, пока все вершины графа не будут окрашены. При этом для графа G будет построено покрывающее дерево с корнем в вершине s (если такое дерево сущест­вует). В вершину s не ведет ни одна дуга и существует ориентированный путь из s в любую другую вершину графа.

Пример. Найти кратчайший путь между вершинами s и t для графа, изображенного на рис. 1.19

Окрасим вершину s положим для любого и . Легко найти, что ,

Окрашиваем вершину c дугу (s, с), так как вели­чина d(c) минимальна. Полагаем у=с и, поскольку вер­шина t не окрашена, снова пересчитываем величину d(x). Имеем:

Окрашиваем вершину а и дугу (s, a). Полагаем у=а и пересчитываем величины d(x). Получаем ,

Окрашиваем вершину b и дугу (a, b). Полагаем y=b, находим величины

Окрашиваем вершину d и дугу (a, d) [либо дугу (с, d)]. Полагаем y=d и находим величину d(t)=13

Окрашиваем вершину t. Кратчайшим является путь (s, b, t), Покрывающее дерево кратчайших путей изобра­жено на рис. 1.20.

Обобщим алгоритм на тот случай, когда некоторые дуги имеют отрицательные длины. При выполнении шага 2 алгоритма пересчет вели­чин d(x) производят для всех вершин.

Если для некоторой окрашенной вершины вели­чина d(x) уменьшается, то с нее и с инцидентной ей дуги окраску снимают.

Процесс вычислений заканчивают, когда все вер­шины графа G окрашены и ни одно из чисел d(x) не меняется при пересчете.

Пример. На рис. 1.21 изображен граф, имеющий дугу отрицательной длины. Найти кратчайший путь между вершинами s я t.

Окрашиваем вершину s. Полагаем , пересчитываем величины d(x): .

Окрашиваем вершину t, дугу(s, t) и полагаем y=t. Пересчитываем числа d(x). Поскольку из вершины t не исходит на одна дуга, эти числа не меняются.

Окрашиваем вершину а и дугу (s, а). Полагаем у=a и пересчитываем d(x): . Величина d(t) уменьшилась, поэтому с вершины t и дуги (s, t) окраску снимаем.

В исходном графе неокрашенной является только вер­шина t. Она окрашивается вместе с дугой (a, t), по­скольку у=а.

Полагая y=t, пересчитываем величины d(x), но они не меняются. Кратчайшим является путь (s, a, t).

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

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

Дано: непустой взвешенный граф G=(V, E) с произвольными весами ребер (дуг) - . Требуется найти длины кратчайших путей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.

Инициализация:

1. Построим матрицу размерности , элементы которой определяются по правилу:

dij0= a(vi, vj), где i<>j, если в графе существует ребро (дуга) (vi, vj);

, где i<>j, если нет ребра (дуги) (vi, vj).

2. m = 0.

Основная часть:

1. Построим матрицу Dm+1 по Dm, вычисляя ее элементы следующим образом:

dijm+1=min{dijm, di(m+1)m + d(m+1)jm}, где i<>j; diim+1=0 (*).

Если dimm + dmim < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину vi. Выход.

2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D|V| равны длинам кратчайших путей между соответствующими вершинами. Выход.

Конец.

Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов pij=i. Каждый раз, когда на шаге (1) значение dijm+1 будет уменьшаться в соответствии с (*) (т. е. когда di(m+1)m + d(m+1)jm<dijm), выполним присваивание pij:=p(m+1)j. В конце работы алгоритма матрица P будет определять кратчайшие пути между всеми парами вершин: значение pij будет равно номеру предпоследней вершины в пути между i и j (либо pij=i, если путь не существует).