amp; weight, int start, int end)
{ lt; vector lt; int gt; gt; matr=weight; n=matr.size (); (int p=0; p lt; n; p ++) (int m=0; m lt; n; m ++) (matr [m] [p] lt; 0) [m] [p]=-matr [m] [p]; lt; vector lt; int gt; gt; temp (n, vector lt; int gt; (2)); (int i=0; i lt; n; i ++)
temp [i] [0]=LONG_MAX; [start] [1]=1;//робимо постійну мітку на початку
temp [start] [0]=0;//значення (matr, temp, start, end); [end] [0];
}
де функція Work:
void Work (vector lt; vector lt; int gt; gt; amp; matr, vector lt; vector lt; int gt; gt; amp; temp, int start, int end)
{st=start; (st!=end)
{m=LONG_MAX; if (temp [end] [1]!=0) return; (int i=0; i lt; 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 lt; temp.size (); k ++)
{(temp [k] [1] == 0 amp; amp; temp [k] [0] == min (temp [k] [0], m))
{= k; m=temp [k] [0];
}
} [st] [1]=1;
}}
Другий етап.
void Path (vector lt; vector lt; int gt; gt; amp; matr, int lenght, int start, int end, list lt; int gt; amp; path) {// рекурсивне заповнення шляху (1 крок -одна вершина) n=matr.size (), tmp; lt; vector lt; int gt; gt; tmatr (matr); b=true, tp=false; (int i=0; b; i ++)
{(start == i amp; amp; matr [i] [end] == lenght) return; =tmatr[end][i];[end][i]=0;((matr[i][end]!=0)amp;amp;(matr[i][end]!=lenght)amp;amp;(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);
} lt; int gt; MakePath (vector lt; vector lt; int gt; gt; amp; matr, int lenght, int start, int end)
{(start == end) return list lt; int gt; (0); lt; int gt; path; (matr, lenght, start, end, path) ;. push_front (start) ;. push_back (end);
return path;
}
Результати роботи програми
Приклад роботи програми буде приводитися на зв'язковому орієнтованому графі, сформованим з розподілу Пойа - 1.
Рис1. Приклад роботи програми: виведення розподілу і матриці получившегося графа.
Рис2. Приклад роботи програми: виведення матриці вартості вершин, отриманої випадковим чином
Рис3. Приклад роботи програми: виведення матриці пропускної здатності, отриманої випадковим чином
Ріс4. Приклад роботи програми: виведення результату роботи алгоритму Фалкерсона.
рис5. Приклад роботи програми: обчислення потоку мінімальної вартості.
Ріс6. Приклад роботи програми: виведення матриці потоків, отриманої після пропускання потоку заданої вартості.
Висновок
У даній роботі був сформований зв'язний ациклічний граф відповідно до розподілу Пойа - 1. Матриці вартості та пропускної здатності реалізовані шляхом заміни одиниць в матриці суміжності на числа, отримані випадковим чином. Для отриманого графа був знайдений максимальний потік за допомогою теореми Форда-Фалкерсона. Максимальний потік шукається за допомогою алгоритму Беллмана - Форда, що відрізняється від класичного методу, що використовує пошук в глибину.
Далі був реалізований пошук мінімальної вартості для заданого потоку в мережі. Такий пошук мінімальної вартості актуальний для вирішення багатьох завдань на логістику, наприклад для вирішення завдань, пов'язаних з транспортною мережею.
В якості величини потоку брали 2/3 від максимального потоку. Пошук мінімальних за вартістю шляхів проводився за допомогою алгоритмів Беллмана - Форда і Дейкстри. Алгоритм Дейкстри краще використовувати за умови, що граф не має негативні ваги, так як він працює швидше, ніж алгоритм Беллмана-Форда. Для більш спільного рішення потрібно використовувати алгоритм Беллмана-Форда. З кожним кроком відбувається модифікація мережі з урахуванням пропустити потоку. Модифікація полягає в зміні матриць вартостей і пропускних спроможностей після кожної ітерації.
В результаті роботи програми ми отримуємо матрицю потоків, з якої видно по якомусь ребру який потік пройшов. Загальна сума потоку обчислюється за допомогою матриці потоків і первісної матриці вартості і також виводитьс...
