Едмондс–Карпов алгоритам је имплементација Форд-Фулкерсоновог алгоритма за израчунавање максималног протока у транспортном проблему у времену . Алгоритам је први пут објавио Јефим Диниц 1970. године и самостално су објавили Џек Едмондс и Ричард Карп 1972. године. Алгоритам обухвата додатне технике које смањују време извршавања на . Алгоритам Алгоритам је идентичан Форд-Фулкерсон алгоритму осим што је дефинисан редослед приликом претраживања. Пронађени пут мора бити најкраћи пут који има расположиве капацитете. То се може постићи претрагом у ширину када ставимо да гране имају јединичну дужину. Време извршавања је пронађено показивањем да се свака увећавајућа путања може наћи у времену јер сваки пут најмање једна од грана постаје засићена (грана која има максимални могући проток) и да је дужина највише . Друго својство овог алгоритма је да се дужина најкраће увећавајуће путање увећава монотоно. Доказ се може пронаћи у књизи Introduction to Algorithms.

Имплементација

Псеудокод

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

Имплементација у C++ #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 и капацитетима као што су приказани:

300px

У паровима записаним на гранама, је тренутан проток, а је капацитет.

Преостали капацитет од до је . Ако је проточни граф од до негативан, он доприноси преосталом капацитету.

Капацитет Пут Резултујућа мрежа 300px</td> 300px</td> 300px</td> 300px</td>

Приметимо да дужина увећавајуће путање пронађена овим алгоритмом никада не опада. Пронађени пут је најкраћи могући. Пронађени проток је једнак капацитету кроз граф чији су извор и циљ исечени. Постоји само једно минимално сечење у овом графу, партиционисањем чворова у скупове и , са капацитетом:

Референце

Литература

Категорија:Проточни граф Категорија:Графовски алгоритми