Материал: Потоки в сетях

Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

Возвращаемся на шаг 2.

Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго.

Реализация алгоритма

#include "main.h"

int min(int a, int b){(a == 0) return b;(b == 0) return a;(a < b) ? a : b;}Svyazn(vector<vector<int>>& matr){<vector<int>> temp(matr);n = matr.size();(int i = 0; i < n; i++)(int j = 0; j < n; j++)(int k = 0; k < n; k++)(i != k && i != j && temp[j][i] != 0 && temp[i][k] != 0 && (min(temp[j][k], (temp[j][i] + temp[i][k])) != temp[j][k]))[j][k] = temp[j][i] + temp[i][k];(int i = 1; i < n; i++)(!temp[0][i]) return false;true;}Falkerson(vector<vector<int>> propSpos, vector<int> s, vector<int> t){n = propSpos.size(), max = 0, ti = 0, tj = 0, minPath, temp;<vector<int>> rezult(n, vector<int>(n));<int> minP;{= Bellman(propSpos, s[0], t[0]);//= 0;= 0;(int i = 0; i < s.size(); i++)(int j = 0; j < t.size(); j++)(min(minPath, Bellman(propSpos, s[i], t[j])) != minPath)//

{= Bellman(propSpos, s[i], t[j]);//= i;= j;

}= MakePath(propSpos, minPath, s[ti], t[tj]);//= propSpos[*minP.begin()][*++minP.begin()];(list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{++;(min(propSpos[*it][*jt], temp) != temp)= propSpos[*it][*jt];

}= 0;(list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{++;+= propSpos[*it][*jt] * temp;//[*it][*jt] -= temp;[*it][*jt] += temp;(!propSpos[*jt][*it] && propSpos[*it][*jt])[*jt][*it] += temp;(!propSpos[*it][*jt] && !rezult[*jt][*it])[*it][*jt] = 0;

}+= temp;

}while (Svyazn(propSpos));//max;

}

Алгоритм Беллмана - Форда

Алгоритм Беллмана-Форда - алгоритм поиска кратчайшего пути во взвешенном графе. Он имеет сложность О(p*q) - это худший случай и сложность О(р) в лучшем случае. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом, но его ограничением является то, что на входе должен быть граф без циклов с отрицательным весом. В нашем случае на вход функции идет порядковый номер вершин, между которыми будет происходить поиск кратчайшего пути.

В отличие от алгоритма Дейкстры в этом алгоритме нет постоянных меток, но есть очередь. Сначала берется стартовая вершина и заносится в очередь. Расстояние до остальных вершин предполагается равным бесконечности (то есть константа LONG_MAX в нашей программе).

Шаг алгоритма. Удаляем вершину из начала очереди. Для каждой соседней вершины корректируем метку по формуле из шага алгоритма Дейкстры. Если при этом новое значение меньше старого, то корректируем очередь, иначе продолжаем перебор вершин и корректировку временных меток.

Корректировка очереди. Если раньше вершина не была в очереди, то ее ставим в конец, а если была или находится в данный момент, то ставим ее в начало очереди.

Алгоритм работает, пока очередь не станет пустой, т.е. пока из очереди можно взять вершину.

Реализация алгоритма:

int Bellman(vector<vector<int>>& matr, int start, int end)

{n = matr.size();t;<vector<int>> temp(n, vector<int>(2));(int i = 0; i < n; i++)[i][0] = LONG_MAX;<int> queue;.push_back(start);[start][1] = 1;[start][0] = 0; (queue.size() != 0)

{= *queue.begin();.erase(queue.begin());(int i = 0; i < matr.size(); i++)

{//для каждой вершины(matr[t][i] != 0)

{[i][0];[t][0] + matr[t][i];(min(temp[i][0], min(temp[i][0], temp[t][0] + matr[t][i])) != temp[i][0])

{[i][0] = temp[t][0] + matr[t][i];(temp[i][1]).insert(queue.begin(),i);

{.push_back(i);//Иначе - в конец[i][1] = 1;

}}}}}temp[end][0];}

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

Работу алгоритма можно разделить на два этапа:

Первый этап: Присвоение вершинам начальных меток.

Каждой вершине сопоставим метку - расстояние от этой вершины до начальной вершины. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Метка начальной вершины полагается равной 0, метки остальных вершин - бесконечности (роль бесконечности выполняет константа LONG_MAX, равная 2147483647L). Бесконечность значит, что расстояния от начальной вершины до других пока неизвестны. Все вершины графа, кроме начальной, помечаются как не посещённые.

Шаг алгоритма.

Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Для каждой соседней вершины u, кроме посещённых, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с соседней вершиной. Если полученное значение длины меньше значения метки соседней вершины, заменим значение метки полученным значением длины. Рассмотрев все соседние вершины, пометим вершину u как посещенную и повторим шаг алгоритма.
В нашем случае нужно найти кратчайшее расстояние между заданными вершинами, поэтому на входе две вершины, а не одна.

Второй этап: Построение кратчайшего пути.

Среди вершин, непосредственно предшествующих текущей, с постоянной меткой, ищем вершину, удовлетворяющую соотношению:

где  метка вершины,  вес ребра, текущая вершина, которая добавляется в маршрут.

Реализация алгоритма:

Первый этап

int Deykstra(vector<vector<int>>& weight, int start, int end)

{<vector<int>> matr = weight;n = matr.size();(int p = 0; p < n; p++)(int m = 0; m < n; m++)(matr[m][p]<0)[m][p]= -matr[m][p];<vector<int>> temp (n, vector<int>(2));(int i = 0; i < n; i++)

temp[i][0] = LONG_MAX;[start][1] = 1;//делаем постоянную метку в начале

temp[start][0] = 0;// значение(matr, temp, start, end);[end][0];

}

где функция Work:

void Work(vector<vector<int>>& matr, vector<vector<int>>& temp, int start, int end)

{st = start;(st != end)

{m = LONG_MAX;if (temp[end][1] != 0) return;(int i = 0; i < matr.size(); i++)

{++;(matr[st][i] != 0)(temp[i][1] == 0)[i][0] = min(temp[i][0], temp[st][0] + matr[st][i]);

}(int k = 0; k < temp.size(); k++)

{(temp[k][1] == 0 && temp[k][0] == min(temp[k][0], m))

{= k;m = temp[k][0];

}

}[st][1] = 1;

}}

Второй этап.

void Path(vector<vector<int>>& matr, int lenght, int start, int end, list<int>& path){//рекурсивное заполнение пути (1 шаг - одна вершина)n=matr.size(), tmp;<vector<int>> tmatr (matr);b=true, tp=false;(int i=0; b; i++)

{(start==i&&matr[i][end]==lenght)return; = tmatr[end][i];[end][i]=0;((matr[i][end]!=0)&&(matr[i][end]!=lenght)&&(Bellman(tmatr,start,i)==lenght-matr[i][end]))

{.push_front(i);-= matr[i][end];= i;= false;

}tmatr[end][i] = tmp;

}(tmatr ,lenght, start, end, path);

}<int> MakePath(vector<vector<int>>& matr, int lenght, int start, int end)

{(start==end) return list<int>(0);<int> path;(matr,lenght, start, end, path);.push_front(start);.push_back(end);

return path;

}

Результаты работы программы

Пример работы программы будет приводиться на связном ориентированном графе, сформированным по распределению Пойа-1.

Рис1. Пример работы программы: вывод распределения и матрицы получившегося графа.

Рис2. Пример работы программы: вывод матрицы стоимости вершин, полученной случайным образом

Рис3. Пример работы программы: вывод матрицы пропускной способности, полученной случайным образом

Рис4. Пример работы программы: вывод результата работы алгоритма Фалкерсона.

Рис5. Пример работы программы: вычисление потока минимальной стоимости.

Рис6. Пример работы программы: вывод матрицы потоков, полученной после пропускания потока заданной стоимости.

Заключение

В данной работе был сформирован связный ациклический граф в соответствии с распределением Пойа-1. Матрицы стоимости и пропускной способности реализованы путем замены единиц в матрице смежности на числа, полученные случайным образом. Для полученного графа был найден максимальный поток с помощью теоремы Форда-Фалкерсона. Максимальный поток ищется при помощи алгоритма Беллмана - Форда, что отличается от классического метода, использующего поиск в глубину.

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

В качестве величины потока брали 2/3 от максимального потока. Поиск минимальных по стоимости путей производился с помощью алгоритмов Беллмана - Форда и Дейкстры. Алгоритм Дейкстры лучше использовать при условии, что граф не имеет отрицательные веса, так как он работает быстрее, чем алгоритм Беллмана-Форда. Для более общего решения нужно использовать алгоритм Беллмана-Форда. С каждым шагом происходит модификация сети с учетом пропустившегося потока. Модификация заключается в изменении матриц стоимостей и пропускных способностей после каждой итерации.

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

В графе может быть несколько истоков и стоков, а нужно по одному, поэтому используются фиктивные исток и сток, объединяющие в себя реальные стоки и истоки.

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

Чтобы модифицировать эту программу, можно добавить визуализацию графа и каждого изменения матриц стоимости и пропускной способности, прослеживая распределения потоков. В программе мы пропускаем 2/3 от максимального потока, а можно предоставить выбор пропускаемого потока пользователю, не допуская возможность пустить поток больше максимального.

Список использованной литературы

Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. - СПБ.: Питер, 2009. - 384 с.

Вадзинский Р.Н. Справочник по вероятностным распределениям. - СПб.: Наука, 2001. - 295 с.