Ford-Fulkerson-Algorithmus

Inhaltsverzeichnis

Verwendete Terminologien
Wie funktioniert der Ford-Fulkerson-Algorithmus?
Ford-Fulkerson-Beispiel
Beispiele für Python, Java und C / C ++
Ford-Fulkerson-Anwendungen

In diesem Tutorial erfahren Sie, was der Ford-Fulkerson-Algorithmus ist. Außerdem finden Sie Arbeitsbeispiele zum Ermitteln des maximalen Flusses in einem Flussnetzwerk in C, C ++, Java und Python.

Der Ford-Fulkerson-Algorithmus ist ein gieriger Ansatz zur Berechnung des maximal möglichen Flusses in einem Netzwerk oder einer Grafik.

Ein Begriff, Flussnetzwerk , wird verwendet, um ein Netzwerk von Eckpunkten und Kanten mit einer Quelle (S) und einer Senke (T) zu beschreiben. Jeder Scheitelpunkt außer S und T kann eine gleiche Menge an Material empfangen und senden. S kann nur senden und T kann nur Sachen empfangen.

Wir können das Verständnis des Algorithmus anhand eines Flüssigkeitsflusses in einem Netzwerk von Rohren mit unterschiedlichen Kapazitäten visualisieren. Jedes Rohr hat eine bestimmte Flüssigkeitskapazität, die es auf einmal übertragen kann. Für diesen Algorithmus werden wir herausfinden, wie viel Flüssigkeit an einer Instanz über das Netzwerk von der Quelle zur Senke fließen kann.

Flussnetzwerkdiagramm

Verwendete Terminologien

Erweiterungspfad

Dies ist der in einem Flussnetzwerk verfügbare Pfad.

Restgraph

Es stellt das Flussnetz dar, das einen zusätzlichen möglichen Fluss hat.

Restkapazität

Dies ist die Kapazität der Kante nach Subtraktion des Durchflusses von der maximalen Kapazität.

Wie funktioniert der Ford-Fulkerson-Algorithmus?

Der Algorithmus folgt:

Initialisieren Sie den Fluss in allen Kanten auf 0.
Fügen Sie diesen Pfad dem Fluss hinzu, während sich zwischen der Quelle und der Senke ein Erweiterungspfad befindet.
Aktualisieren Sie das Restdiagramm.

Bei Bedarf können wir auch den umgekehrten Pfad in Betracht ziehen, da wir möglicherweise nie einen maximalen Durchfluss finden, wenn wir sie nicht berücksichtigen.

Die obigen Konzepte können mit dem folgenden Beispiel verstanden werden.

Ford-Fulkerson-Beispiel

Der Fluss aller Kanten ist am Anfang 0.

Beispiel für ein Flussnetzwerkdiagramm

Wählen Sie einen beliebigen Pfad von S nach T. In diesem Schritt haben wir den Pfad SABT ausgewählt. Pfad suchen
Die Mindestkapazität zwischen den drei Kanten beträgt 2 (BT). Aktualisieren Sie auf dieser Grundlage den Fluss / die Kapazität für jeden Pfad. Aktualisieren Sie die Kapazitäten
Wählen Sie einen anderen Pfad SDCT. Die Mindestkapazität zwischen diesen Kanten beträgt 3 (SD). Nächsten Pfad
suchen Aktualisieren Sie die Kapazitäten entsprechend. Aktualisieren Sie die Kapazitäten
Betrachten wir nun auch den umgekehrten Pfad BD. Pfad SABDCT auswählen. Die minimale Restkapazität zwischen den Kanten beträgt 1 (DC). Nächsten Pfad
suchen Kapazitäten aktualisieren. Aktualisieren der Kapazitäten
Die Kapazität für Vorwärts- und Rückwärtspfade wird separat betrachtet.
Addieren aller Flows = 2 + 3 + 1 = 6, was der maximal mögliche Flow im Flow-Netzwerk ist.

Beachten Sie, dass dieser Pfad nicht verwendet werden kann, wenn die Kapazität für eine Kante voll ist.

Beispiele für Python, Java und C / C ++

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; )