Транспортна мрежа е ориентиран граф, без циклуси во кој на секое ребро (i, j) му е придружен реален број аij>=0 што се нарекува пропусна способност на реброто, и за кој важи
- постои едно и само едно теме s, за кое важи дека нема ребра што влегуваат во тоа теме, кое се нарекува влезно теме или влез на мрежата
- постои едно и само едно теме t за кое важи дека нема ребра кои што излегуваат од тоа теме, кое се нарекува излезно теме или излез од мрежата
За секое теме освен влезното и излезното важи дека вкупниот проток што влегува во темето е еднаков со вкупниот проток што излегува од темето
Алгоритмот за наоѓање максимален проток од влезот (s) до излезот (t) е следен:
Алгоритмот ја започнува работата со произволен проток, што може да биде и нулти поток (се ставаат сите моментални проводности на нула). Потоа, протокот постојано се зголемува со систематска проверка на сите аугментални патеки од s кон t. Барањето на овие аугментални патеки се прави со помош на доделување ознаки на темињата кои кажуваат во правец на кои ребра и за колку потокот може да биде зголемен. Така, потокот се зголемува за максимално можна вредност и потоа повторно се ажурираат ознаките на темињата. Постапката се повторува се додека има аугментални патеки од s кон t.
Овој алгоритам е познат како алгоритам на Форд-Фалкерсон и доколку потокот секогаш го зголемуваме по најкусата аугментална патека, максималниот поток се добива за помалку од |V|*|E|/2 итерации каде што со V го означуваме бројот на темиња, а со E бројот на ребра во графот.
Имплементацијата во Java е следна:
static int M; // M is the number of vertices
static long c[][] = new long[50][50];
static long f[][] = new long[50][50]; // the flow
static boolean busy[] = new boolean[50];
static long ver[] = new long[50];
static int who[] = new int[50];
static void updateNeighbours(int mom) {
int i;
long newver;
for (i=1;i<=M;i++) {
if (busy[i] == false) {
newver = Math.min(ver[mom], c[mom][i]-f[mom][i]);
if (newver > ver[i]) {
ver[i] = newver;
who[i] = mom;
}
}
}
}
static boolean findPath() {
// we set all the vertices as unvisited
int i;
int bestv;
long bestscore;
long dec;
for (i=1;i<=M;i++) {
busy[i] = false;
ver[i] = 0;
}
busy[1] = true;
ver[1] = Integer.MAX_VALUE;
who[1] = 0;
updateNeighbours(1);
while (busy[M] == false) {
// we find the best vertex found so far
bestv = 0;
bestscore = 0;
for (i=1;i<=M;i++) {
if (busy[i] == false) {
if (ver[i] > bestscore) {
bestscore = ver[i];
bestv = i;
}
}
}
if (bestv == 0) {
// this means that a path has not been found
return false;
}
busy[bestv] = true;
updateNeighbours(bestv);
}
dec = ver[M];
i = M;
while (i!=1) {
// we work with the segment from i to who[i]
f[who[i]][i]+=dec;
f[i][who[i]]=-f[who[i]][i];
i=who[i];
}
return true;
}
static void networkFlow() {
while (findPath() == true) {
}
}
M е бројот на темиња.
c[i][j] е пропусната способност на реброто од i до j.
f[i][j] е моменталната проводност по патот од i до j.
Пред да се повика функцијата networkFlow() треба да се иницијализираат пропусните способности на сите ребра. Доколку нема пат од едно теме i до друго теме j тогаш c[i][j]=0. Доколку графот е насочен, т.е. може да се оди само од i до j тогаш само c[i][j] > 0, а c[j][i] = 0. Доколку може да се оди во двете насоки тогаш c[i][j] == c[j][i] > 0. Треба да се напомене дека при повикувањето на networkFlow(), сите елементи f[i][j] треба да бидат иницијализирани на нула.
busy[], ver[] и who[] се низи кои се потребни за работа на алгоритмот на Дијкстра (правилниот изговор е Диџкстра, но јас го викам Дијкстра :) со кој го наоѓаме патот од изворот до излезното теме.
Овој алгоритам може да се примени и за други проблеми, како што е bipartite matching problem. Проблемот може да се дефинира вака.
Дадени ни се група на машки и група на женски и дадено ни е кој со кој си одговара :)
Да се одреди максималниот број на парови што можат да бидат направени така што да си одговараат машкото и женското од секој пар :)
Како може да го решиме проблемот со помош на тоа што веќе го знаеме за транспортните мрежи? Земаме две темиња кои ќе бидат влезно и излезно теме. Сите темиња од групата машки ги поврзуваме со изворот, а сите темиња од групата женски ги поврзуваме со излезното теме. Ги поврзуваме само оние машки и женски кои си одговараат. Сите врски се со тежина 1, т.е. доколку темињата i и j се поврзани, тогаш c[i][j] = 1.
Објаснувањето зошто треба вака да се реши проблемот го оставам на вас :)
Алгоритмот за решавање на овој проблем на транспортни мрежи многу често се применува во задачи. Многу убаво објаснување за овој алгоритам и за многу други, заедно со задачи со нивна примена може да се најдат на сајтот на USACO. Во скоро време ќе напишам и повеќе околу овој сајт и тоа што тој го нуди за едукација.
Користена литература:
USACO
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Algorithms in C - Robert Sedgewick
