Ebben az oktatóanyagban megtudhatja, mi a Ford-Fulkerson algoritmus. Működő példákat is talál a maximális áramlás megtalálására egy áramlási hálózatban C, C ++, Java és Python.
A Ford-Fulkerson algoritmus kapzsi megközelítés a hálózatban vagy egy grafikonban a lehető legnagyobb áramlás kiszámításához.
Az áramlási hálózat kifejezés a csúcsok és élek hálózatának leírására szolgál egy forrás (S) és egy mosogató (T) segítségével. Az S és T kivételével minden csúcs azonos mennyiségű cuccot tud fogadni és küldeni rajta. S csak küldeni tud, T pedig csak cuccokat fogadni.
Vizualizálhatjuk az algoritmus megértését a különböző kapacitású csövek hálózatán belüli folyadékáram felhasználásával. Minden csőnek van egy bizonyos kapacitása folyadékot, amelyet egy példányon át tud szállítani. Ehhez az algoritmushoz meg fogjuk találni, hogy mennyi folyadék áramolhat a forrásból a mosogatóba egy példányon a hálózat segítségével.
Folyamatos hálózati grafikon
Használt terminológiák
Bővítő Path
Ez egy áramlási hálózatban elérhető útvonal.
Maradék grafikon
Az az áramlási hálózat, amely további lehetséges áramlással rendelkezik.
Maradék kapacitás
Ez az él kapacitása, miután levonták az áramlást a maximális kapacitásból.
Hogyan működik a Ford-Fulkerson algoritmus?
Az algoritmus a következő:
- Inicializálja az összes él szélét 0-ra.
- Míg a forrás és a mosogató között van egy bővítő út, add hozzá ezt az utat az áramláshoz.
- Frissítse a maradék grafikont.
Szükség esetén figyelembe vehetjük a fordított utat is, mert ha nem vesszük figyelembe őket, akkor soha nem találhatunk maximális áramlást.
A fenti fogalmak az alábbi példával érthetők meg.
Ford-Fulkerson példa
Az összes él áramlása kezdetben 0.
Példa áramlási hálózati grafikonra
- Válasszon tetszőleges útvonalat S-től T-ig. Ebben a lépésben kiválasztottuk a SABT utat.
Keressen egy utat
A három él közötti minimális kapacitás 2 (BT). Ennek alapján frissítse az egyes utak áramlását / kapacitását.
Frissítse a kapacitásokat - Válasszon másik útvonalat SDCT. Az élek között a minimális kapacitás 3 (SD).
Keresse meg a következő utat
Ennek megfelelően frissítse a kapacitásokat.
Frissítse a kapacitásokat - Most vegyük figyelembe a BD fordított utat is. A SABDCT útvonal kiválasztása. Az élek közötti minimális maradék kapacitás 1 (DC).
Keresse meg a következő utat
A kapacitások frissítése.
Frissítse a kapacitásokat
Az előremenő és a hátramenet kapacitása külön-külön kerül figyelembe vételre. - Összeadva az összes áramlást = 2 + 3 + 1 = 6, ami a maximális lehetséges áramlás az áramlási hálózaton.
Vegye figyelembe, hogy ha bármelyik él kapacitása megtelt, akkor ez az út nem használható.
Példák Python, Java és 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; )
Ford-Fulkerson alkalmazások
- Vízelosztó vezeték
- Kétoldalas illesztési probléma
- Forgalom igényekkel
