Algorytm Forda-Fulkersona

Spisie treści

Używane terminologie
Jak działa algorytm Forda-Fulkersona?
Przykład Forda-Fulkersona
Przykłady w Pythonie, Javie i C / C ++
Aplikacje Ford-Fulkerson

W tym samouczku dowiesz się, czym jest algorytm Forda-Fulkersona. Znajdziesz także działające przykłady znalezienia maksymalnego przepływu w sieci przepływu w językach C, C ++, Java i Python.

Algorytm Forda-Fulkersona jest chciwym podejściem do obliczania maksymalnego możliwego przepływu w sieci lub grafie.

Termin, sieć przepływu , jest używany do opisania sieci wierzchołków i krawędzi ze źródłem (S) i ujściem (T). Każdy wierzchołek, z wyjątkiem S i T , może odbierać i wysyłać przez niego taką samą ilość rzeczy. S może tylko wysyłać, a T może tylko odbierać rzeczy.

Możemy wizualizować zrozumienie algorytmu za pomocą przepływu cieczy wewnątrz sieci rur o różnych pojemnościach. Każda rura ma określoną pojemność cieczy, którą może jednorazowo przesyłać. W przypadku tego algorytmu ustalimy, ile cieczy można przepłynąć ze źródła do zlewu w instancji za pomocą sieci.

Wykres sieci przepływu

Używane terminologie

Augmenting Path

Jest to ścieżka dostępna w sieci przepływu.

Wykres reszt

Reprezentuje sieć przepływów, która ma dodatkowy możliwy przepływ.

Pozostała pojemność

Jest to pojemność krawędzi po odjęciu przepływu od wydajności maksymalnej.

Jak działa algorytm Forda-Fulkersona?

Algorytm jest następujący:

Zainicjuj przepływ na wszystkich krawędziach na 0.
Chociaż między źródłem a zlewem istnieje ścieżka zwiększająca się, dodaj tę ścieżkę do przepływu.
Zaktualizuj wykres reszt.

W razie potrzeby możemy również rozważyć odwrotną ścieżkę, ponieważ jeśli ich nie uwzględnimy, możemy nigdy nie znaleźć maksymalnego przepływu.

Powyższe koncepcje można zrozumieć na poniższym przykładzie.

Przykład Forda-Fulkersona

Przepływ wszystkich krawędzi wynosi na początku 0.

Przykładowy wykres sieci przepływu

Wybierz dowolną ścieżkę od S do T. W tym kroku wybraliśmy ścieżkę SABT. Znajdź ścieżkę
Minimalna pojemność między trzema krawędziami wynosi 2 (BT). Na tej podstawie zaktualizuj przepływ / przepustowość dla każdej ścieżki. Zaktualizuj zdolności produkcyjne
Wybierz inną ścieżkę SDCT. Minimalna pojemność między tymi krawędziami wynosi 3 (SD). Znajdź następną ścieżkę
Zaktualizuj pojemności zgodnie z tym. Zaktualizuj zdolności produkcyjne
Rozważmy teraz również BD z odwrotną ścieżką. Wybór ścieżki SABDCT. Minimalna pojemność szczątkowa między krawędziami wynosi 1 (DC). Znajdź następną ścieżkę
Aktualizacja zdolności produkcyjnych. Aktualizacja przepustowości
Pojemność dla ścieżek do przodu i do tyłu jest rozważana osobno.
Dodanie wszystkich przepływów = 2 + 3 + 1 = 6, czyli maksymalny możliwy przepływ w sieci przepływów.

Zwróć uwagę, że jeśli pojemność dowolnej krawędzi jest pełna, nie można użyć tej ścieżki.

Przykłady w Pythonie, Javie i 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; )