Ford-Fulkerson-algoritmi

Tässä opetusohjelmassa opit, mikä on Ford-Fulkerson-algoritmi. Löydät myös toimivia esimerkkejä maksimaalisen virtauksen löytämisestä virtausverkossa C, C ++, Java ja Python.

Ford-Fulkerson-algoritmi on ahne tapa laskea suurin mahdollinen virtaus verkossa tai kuvaajassa.

Termiä, virtausverkkoa , käytetään kuvaamaan pisteiden ja reunojen verkkoa lähteen (S) ja nielun (T) kanssa. Jokainen kärki, paitsi S ja T , voi vastaanottaa ja lähettää saman määrän tavaraa sen läpi. S voi lähettää vain ja T vastaanottaa vain tavaraa.

Voimme visualisoida algoritmin ymmärtämisen käyttämällä nestevirtaa erikapasiteettisten putkien verkon sisällä. Jokaisella putkella on tietty kapasiteetti nestettä, jonka se voi siirtää instanssissa. Tätä algoritmia varten aiomme selvittää, kuinka paljon nestettä voidaan virtaa lähteestä pesualtaaseen verkkoa käyttävässä instanssissa.

Virtauskaavio

Käytetyt terminologiat

Laajentava polku

Se on polku, joka on käytettävissä virtausverkossa.

Jäännöskaavio

Se edustaa virtausverkkoa, jolla on ylimääräinen mahdollinen virtaus.

Jäännöskapasiteetti

Se on reunan kapasiteetti, kun virta on vähennetty maksimikapasiteetista.

Kuinka Ford-Fulkerson-algoritmi toimii?

Algoritmi seuraa:

  1. Alusta virtaus kaikissa reunoissa arvoon 0.
  2. Vaikka lähteen ja pesualtaan välillä on kasvava polku, lisää tämä polku virtaukseen.
  3. Päivitä jäännöskaavio.

Voimme myös harkita käänteistä polkua tarvittaessa, koska jos emme ota niitä huomioon, emme ehkä koskaan löydä suurinta virtausta.

Yllä olevat käsitteet voidaan ymmärtää alla olevan esimerkin avulla.

Esimerkki Ford-Fulkersonista

Kaikkien reunojen virtaus on alussa 0.

Virtauskaavioesimerkki
  1. Valitse mikä tahansa mielivaltainen polku S: stä T: hen. Tässä vaiheessa olemme valinneet polun SABT. Löydä polku
    Kolmen reunan vähimmäiskapasiteetti on 2 (BT). Päivitä tämän perusteella kunkin polun virtaus / kapasiteetti. Päivitä kapasiteetit
  2. Valitse toinen polku SDCT. Pienin kapasiteetti näiden reunojen välillä on 3 (SD). Etsi seuraava polku
    Päivitä kapasiteetit tämän mukaisesti. Päivitä kapasiteetit
  3. Tarkastellaan nyt myös käänteisen polun BD: tä. Valitaan polku SABDCT. Pienin jäännöskapasiteetti reunojen välillä on 1 (DC). Etsi seuraava polku
    Kapasiteettien päivittäminen. Päivitä
    kapasiteetit Eteen- ja paluureittien kapasiteettia tarkastellaan erikseen.
  4. Lisäämällä kaikki virtaukset = 2 + 3 + 1 = 6, mikä on suurin mahdollinen virtaus virtausverkossa.

Huomaa, että jos minkä tahansa reunan kapasiteetti on täynnä, sitä polkua ei voida käyttää.

Python-, Java- ja C / C ++ -esimerkkejä

Python Java C C ++ 
 # Ford-Fulkerson algorith in Python from collections import defaultdict class Graph: def __init__(self, graph): self.graph = graph self. ROW = len(graph) # Using BFS as a searching algorithm def searching_algo_BFS(self, s, t, parent): visited = (False) * (self.ROW) queue = () queue.append(s) visited(s) = True while queue: u = queue.pop(0) for ind, val in enumerate(self.graph(u)): if visited(ind) == False and val> 0: queue.append(ind) visited(ind) = True parent(ind) = u return True if visited(t) else False # Applying fordfulkerson algorithm def ford_fulkerson(self, source, sink): parent = (-1) * (self.ROW) max_flow = 0 while self.searching_algo_BFS(source, sink, parent): path_flow = float("Inf") s = sink while(s != source): path_flow = min(path_flow, self.graph(parent(s))(s)) s = parent(s) # Adding the path flows max_flow += path_flow # Updating the residual values of edges v = sink while(v != source): u = parent(v) self.graph(u)(v) -= path_flow self.graph(v)(u) += path_flow v = parent(v) return max_flow graph = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)) g = Graph(graph) source = 0 sink = 5 print("Max Flow: %d " % g.ford_fulkerson(source, sink))
 // Ford-Fulkerson algorith in Java import java.util.LinkedList; class FordFulkerson ( static final int V = 6; // Using BFS as a searching algorithm boolean bfs(int Graph()(), int s, int t, int p()) ( boolean visited() = new boolean(V); for (int i = 0; i < V; ++i) visited(i) = false; LinkedList queue = new LinkedList(); queue.add(s); visited(s) = true; p(s) = -1; while (queue.size() != 0) ( int u = queue.poll(); for (int v = 0; v 0) ( queue.add(v); p(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph()(), int s, int t) ( int u, v; int Graph()() = new int(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) Graph(u)(v) = graph(u)(v); int p() = new int(V); int max_flow = 0; # Updating the residual calues of edges while (bfs(Graph, s, t, p)) ( int path_flow = Integer.MAX_VALUE; for (v = t; v != s; v = p(v)) ( u = p(v); path_flow = Math.min(path_flow, Graph(u)(v)); ) for (v = t; v != s; v = p(v)) ( u = p(v); Graph(u)(v) -= path_flow; Graph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) public static void main(String() args) throws java.lang.Exception ( int graph()() = new int()() ( ( 0, 8, 0, 0, 3, 0 ), ( 0, 0, 9, 0, 0, 0 ), ( 0, 0, 0, 0, 7, 2 ), ( 0, 0, 0, 0, 0, 5 ), ( 0, 0, 7, 4, 0, 0 ), ( 0, 0, 0, 0, 0, 0 ) ); FordFulkerson m = new FordFulkerson(); System.out.println("Max Flow: " + m.fordFulkerson(graph, 0, 5)); ) )
 / Ford - Fulkerson algorith in C #include #define A 0 #define B 1 #define C 2 #define MAX_NODES 1000 #define O 1000000000 int n; int e; int capacity(MAX_NODES)(MAX_NODES); int flow(MAX_NODES)(MAX_NODES); int color(MAX_NODES); int pred(MAX_NODES); int min(int x, int y) ( return x < y ? x : y; ) int head, tail; int q(MAX_NODES + 2); void enqueue(int x) ( q(tail) = x; tail++; color(x) = B; ) int dequeue() ( int x = q(head); head++; color(x) = C; return x; ) // Using BFS as a searching algorithm int bfs(int start, int target) ( int u, v; for (u = 0; u < n; u++) ( color(u) = A; ) head = tail = 0; enqueue(start); pred(start) = -1; while (head != tail) ( u = dequeue(); for (v = 0; v 0) ( enqueue(v); pred(v) = u; ) ) ) return color(target) == C; ) // Applying fordfulkerson algorithm int fordFulkerson(int source, int sink) ( int i, j, u; int max_flow = 0; for (i = 0; i < n; i++) ( for (j = 0; j = 0; u = pred(u)) ( increment = min(increment, capacity(pred(u))(u) - flow(pred(u))(u)); ) for (u = n - 1; pred(u)>= 0; u = pred(u)) ( flow(pred(u))(u) += increment; flow(u)(pred(u)) -= increment; ) // Adding the path flows max_flow += increment; ) return max_flow; ) int main() ( for (int i = 0; i < n; i++) ( for (int j = 0; j < n; j++) ( capacity(i)(j) = 0; ) ) n = 6; e = 7; capacity(0)(1) = 8; capacity(0)(4) = 3; capacity(1)(2) = 9; capacity(2)(4) = 7; capacity(2)(5) = 2; capacity(3)(5) = 5; capacity(4)(2) = 7; capacity(4)(3) = 4; int s = 0, t = 5; printf("Max Flow: %d", fordFulkerson(s, t)); )
 // Ford-Fulkerson algorith in C++ #include #include #include #include using namespace std; #define V 6 // Using BFS as a searching algorithm bool bfs(int rGraph(V)(V), int s, int t, int parent()) ( bool visited(V); memset(visited, 0, sizeof(visited)); queue q; q.push(s); visited(s) = true; parent(s) = -1; while (!q.empty()) ( int u = q.front(); q.pop(); for (int v = 0; v 0) ( q.push(v); parent(v) = u; visited(v) = true; ) ) ) return (visited(t) == true); ) // Applying fordfulkerson algorithm int fordFulkerson(int graph(V)(V), int s, int t) ( int u, v; int rGraph(V)(V); for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph(u)(v) = graph(u)(v); int parent(V); int max_flow = 0; // Updating the residual values of edges while (bfs(rGraph, s, t, parent)) ( int path_flow = INT_MAX; for (v = t; v != s; v = parent(v)) ( u = parent(v); path_flow = min(path_flow, rGraph(u)(v)); ) for (v = t; v != s; v = parent(v)) ( u = parent(v); rGraph(u)(v) -= path_flow; rGraph(v)(u) += path_flow; ) // Adding the path flows max_flow += path_flow; ) return max_flow; ) int main() ( int graph(V)(V) = ((0, 8, 0, 0, 3, 0), (0, 0, 9, 0, 0, 0), (0, 0, 0, 0, 7, 2), (0, 0, 0, 0, 0, 5), (0, 0, 7, 4, 0, 0), (0, 0, 0, 0, 0, 0)); cout << "Max Flow: " << fordFulkerson(graph, 0, 5) << endl; )

Ford-Fulkerson-sovellukset

  • Vedenjakeluputki
  • Kahdenvälinen sovitusongelma
  • Liikkuminen vaatimusten kanssa

Mielenkiintoisia artikkeleita...