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

Едмондс–Карпов алгоритам је имплементација Форд-Фулкерсоновог алгоритма за израчунавање максималног протока у транспортном проблему у времену $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 .$

Референце

Шаблон:Reflist

Литература

Шаблон:Cite book

Шаблон:Нормативна контрола

[1] Шаблон:Cite journal

[2] Шаблон:Cite journal

[3] Шаблон:Cite book

[1]

[2]

[3]

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

Садржај

Алгоритам

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

Псеудокод

Имплементација у C++

Имплементација у Јави

Пример

Референце

Литература

Мени за навигацију

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

Алгоритам

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

Псеудокод

Имплементација у C++

Имплементација у Јави

Пример

Референце

Литература

Мени за навигацију

Претрага