Едмондс–Карпов алгоритам

Едмондс–Карпов алгоритам је имплементација Форд-Фулкерсоновог алгоритма за израчунавање максималног протока у транспортном проблему у времену $O(|V||E|^{2})$ . Алгоритам је први пут објавио Јефим Диниц 1970. године^[1] и самостално су објавили Џек Едмондс и Ричард Карп 1972. године.^[2] Алгоритам обухвата додатне технике које смањују време извршавања на $O(|V|^{2}|E|)$ .

Алгоритам

Алгоритам је идентичан Форд-Фулкерсон алгоритму осим што је дефинисан редослед приликом претраживања. Пронађени пут мора бити најкраћи пут који има расположиве капацитете. То се може постићи претрагом у ширину када ставимо да гране имају јединичну дужину. Време извршавања $O(|V||E|^{2})$ је пронађено показивањем да се свака увећавајућа путања може наћи у времену $O(|E|)$ јер сваки пут најмање једна од $E$ грана постаје засићена (грана која има максимални могући проток) и да је дужина највише $|V|$ . Друго својство овог алгоритма је да се дужина најкраће увећавајуће путање увећава монотоно. Доказ се може пронаћи у књизи 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

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

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

Преостали капацитет од $u$ до $v$ је $c_{f}(u,v)=c(u,v)-f(u,v)$ . Ако је проточни граф од $u$ до $v$ негативан, он доприноси преосталом капацитету.

Капацитет	Пут
Капацитет	Резултујућа мрежа
$\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))=$ $\min(3-0,2-0,1-0)=$ $\min(3,2,1)=1$	$A,D,E,G$

$\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,6-0,9-0)=$ $\min(2,6,9)=2$	$A,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-0,4-0,1-0,6-2,9-2)=$ $\min(3,4,1,4,7)=1$	$A,B,C,D,F,G$

$\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))=$ $\min(3-1,4-1,2-0,0-(-1),6-3,9-3)=$ $\min(2,3,2,1,3,6)=1$	$A,B,C,E,D,F,G$

Приметимо да дужина увећавајуће путање пронађена овим алгоритмом никада не опада. Пронађени пут је најкраћи могући. Пронађени проток је једнак капацитету кроз граф чији су извор и циљ исечени. Постоји само једно минимално сечење у овом графу, партиционисањем чворова у скупове $\{A,B,C,E\}$ и $\{D,F,G\}$ , са капацитетом: $c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\$

Референце

^ Dinic, E. A. (1970). „Algorithm for solution of a problem of maximum flow in a network with power estimation”. Soviet Math. Doklady. Doklady. 11: 1277—1280.
^ Edmonds, Jack; Karp, Richard M. (1972). „Theoretical improvements in algorithmic efficiency for network flow problems”. Journal of the ACM. Association for Computing Machinery. 19 (2): 248—264. doi:10.1145/321694.321699.
^ Cormen, Thomas H. (2009). „26.2”. Introduction to Algorithms (third изд.). MIT Press. стр. 727–730. ISBN 978-0-262-03384-8.

Литература

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009). „26.2”. Introduction to Algorithms (third изд.). MIT Press. стр. 727–730. ISBN 978-0-262-03384-8.

[1] Dinic, E. A. (1970). „Algorithm for solution of a problem of maximum flow in a network with power estimation”. Soviet Math. Doklady. Doklady. 11: 1277—1280.

[2] Edmonds, Jack; Karp, Richard M. (1972). „Theoretical improvements in algorithmic efficiency for network flow problems”. Journal of the ACM. Association for Computing Machinery. 19 (2): 248—264. doi:10.1145/321694.321699.

[3] Cormen, Thomas H. (2009). „26.2”. Introduction to Algorithms (third изд.). MIT Press. стр. 727–730. ISBN 978-0-262-03384-8.

[1]

[2]

[3]