From Wikipedia, the free encyclopedia
Едмондс–Карпов алгоритам је имплементација Форд-Фулкерсоновог алгоритма за израчунавање максималног протока у транспортном проблему у времену . Алгоритам је први пут објавио Јефим Диниц 1970. године[1] и самостално су објавили Џек Едмондс и Ричард Карп 1972. године.[2] Алгоритам обухвата додатне технике које смањују време извршавања на .
Алгоритам је идентичан Форд-Фулкерсон алгоритму осим што је дефинисан редослед приликом претраживања. Пронађени пут мора бити најкраћи пут који има расположиве капацитете. То се може постићи претрагом у ширину када ставимо да гране имају јединичну дужину. Време извршавања је пронађено показивањем да се свака увећавајућа путања може наћи у времену јер сваки пут најмање једна од грана постаје засићена (грана која има максимални могући проток) и да је дужина највише . Друго својство овог алгоритма је да се дужина најкраће увећавајуће путање увећава монотоно. Доказ се може пронаћи у књизи Introduction to Algorithms.[3]
algoritam EdmondsKarp ulaz: C[1..n, 1..n] (matrica kapaciteta) E[1..n, 1..?] (lista suseda) s (izvor) t (ponor ili cilj) izlaz: f (vrednost maksimalnog protoka) F (matrica koja daje dozvoljen protok sa maksimalnom vrednoscu) f := 0 (inicijalni protok je nula) F := niz(1..n, 1..n) (rezidualni kapacitet od u do v je C[u,v] - F[u,v]) forever m, P := BreadthFirstSearch(C, E, s, t, F) if m = 0 pauza f := f + m (Backtrack pretraga, zapis protoka) v := t while v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u return (f, F)
algoritam PretragaUSirinu ulaz: C, E, s, t, F izlaz: M[t] (kapacitet pronadjenog puta) P (roditeljska tabela) P := niz(1..n) for u in 1..n P[u] := -1 P[s] := -2 (brinemo se da izvor nije ponovo pronadjen) M := niz(1..n) (kapacitet pronadjenog puta do cvora) M[s] := 8 Q := queue() Q.offer(s) while Q.size() > 0 u := Q.poll() for v in E[u] (Ukoliko postoji dostupan kapacitet i v nije vidjeno ranije u pretrazi) if C[u,v] - F[u,v] > 0 and P[v] = -1 P[v] := u M[v] := min(M[u], C[u,v] - F[u,v]) if v ≠ t Q.offer(v) else return M[t], P return 0, P
#include<cstdio>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#define MAX_NODES 100 // maksimalni broj cvorova u grafu
#define INF 2147483646 // reprezentuje beskonacnost
#define UNINITIALIZED -1 // vrednost cvora koji nema roditelja
using namespace std;
// reprezentuje kapacitet grane
int capacities[MAX_NODES][MAX_NODES];
// pokazuje koliko je protoka proteklo kroz granu
int flowPassed[MAX_NODES][MAX_NODES];
// reprezentuje graf. Graf mora da sadrzi i negativne grane!
vector<int> graph[MAX_NODES];
// prikazuje roditelje cvorova puta koji je izgradio BFS
int parentsList[MAX_NODES];
// prikazuje maksimalni protok do cvora u putu koji je izgradio BFS
int currentPathCapacity[MAX_NODES];
int bfs(int startNode, int endNode)
{
memset(parentsList, UNINITIALIZED, sizeof(parentsList));
memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
queue<int> q;
q.push(startNode);
parentsList[startNode]=-2;
currentPathCapacity[startNode]=INF;
while(!q.empty())
{
int currentNode = q.front(); q.pop();
for(int i=0; i<graph[currentNode].size(); i++)
{
int to = graph[currentNode][i];
if(parentsList[to] == UNINITIALIZED)
{
if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
{
// menjamo roditelje buduceg cvora da budu trenutni cvor
parentsList[to] = currentNode;
// proveravamo minimalni rezudualni kapacitet grane do sada
currentPathCapacity[to] = min(currentPathCapacity[currentNode],
capacities[currentNode][to] - flowPassed[currentNode][to]);
// ukoliko smo dostigli poslednji cvor bfs ze zaustavlja
if(to == endNode) return currentPathCapacity[endNode];
// dodajemo nas buduci cvor u red
q.push(to);
}
}
}
}
return 0;
}
int edmondsKarp(int startNode, int endNode)
{
int maxFlow=0;
while(true)
{
// pronalazimo uvecavajucu putanju i maksimalni protok koji mu odgovara
int flow=bfs(startNode, endNode);
// ukoliko ne mozemo da pronadjemo vise puteva protok ce biti 0
if(flow==0)
{
break;
}
maxFlow +=flow;
int currentNode=endNode;
// azuriramo matricu protoka
while(currentNode != startNode)
{
int previousNode = parentsList[currentNode];
flowPassed[previousNode][currentNode] += flow;
flowPassed[currentNode][previousNode] -= flow;
currentNode=previousNode;
}
}
return maxFlow;
}
int main()
{
int nodesCount, edgesCount;
cin>>nodesCount>>edgesCount;
int source, sink;
cin>>source>>sink;
for(int edge=0; edge<edgesCount; edge++)
{
int from, to, capacity;
cin>>from>>to>>capacity;
capacities[from][to]=capacity;
graph[from].push_back(to);
//dodavanje negativne grane
graph[to].push_back(from);
}
int maxFlow = edmondsKarp(source, sink);
cout<<maxFlow<<endl;
return 0;
}
import java.util.*;
/**
* Pronalazi maksimalni protok u mreži protoka
* @param E lista suseda
* @param C matrica kapaciteta (mora biti n x n)
* @param s izvor
* @param t poniranje
* @return maksimalni protok
*/
public class EdmondsKarp {
public static int edmondsKarp(int[][] E, int[][] C, int s, int t) {
int n = C.length;
// Rezudualna kapacitivnost od u do v je C[u][v] - F[u][v]
int[][] F = new int[n][n];
while (true) {
int[] P = new int[n]; // roditeljska tabela
Arrays.fill(P, -1);
P[s] = s;
int[] M = new int[n]; // kapacitet putanje do cvora
M[s] = Integer.MAX_VALUE;
// BFS red
Queue<Integer> Q = new LinkedList<Integer>();
Q.offer(s);
LOOP:
while (!Q.isEmpty()) {
int u = Q.poll();
for (int v : E[u]) {
// ukoliko postoji dostupan kapacitet,
// i v nije vidjeno ranije u pretrazi
if (C[u][v] - F[u][v] > 0 && P[v] == -1) {
P[v] = u;
M[v] = Math.min(M[u], C[u][v] - F[u][v]);
if (v != t)
Q.offer(v);
else {
// Backtrack pretraga, i zapis protoka
while (P[v] != v) {
u = P[v];
F[u][v] += M[t];
F[v][u] -= M[t];
v = u;
}
break LOOP;
}
}
}
}
if (P[t] == -1) { //ukoliko nismo pronasli put do t
int sum = 0;
for (int x : F[s])
sum += x;
return sum;
}
}
}
}
Дат је граф са седам чворова, са извором A, циљем G и капацитетима као што су приказани:
У паровима записаним на гранама, је тренутан проток, а је капацитет.
Преостали капацитет од до је . Ако је проточни граф од до негативан, он доприноси преосталом капацитету.
Приметимо да дужина увећавајуће путање пронађена овим алгоритмом никада не опада. Пронађени пут је најкраћи могући. Пронађени проток је једнак капацитету кроз граф чији су извор и циљ исечени. Постоји само једно минимално сечење у овом графу, партиционисањем чворова у скупове и , са капацитетом:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.