Пређи на садржај

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

С Википедије, слободне енциклопедије

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

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

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

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

Капацитет Пут
Резултујућа мрежа

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

Референце

[уреди | уреди извор]
  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. 

Литература

[уреди | уреди извор]