Σε αυτό το σεμινάριο, θα μάθετε τι είναι ο αλγόριθμος Ford-Fulkerson. Επίσης, θα βρείτε λειτουργικά παραδείγματα εύρεσης μέγιστης ροής σε δίκτυο ροής σε C, C ++, Java και Python.
Ο αλγόριθμος Ford-Fulkerson είναι μια άπληστη προσέγγιση για τον υπολογισμό της μέγιστης δυνατής ροής σε ένα δίκτυο ή ένα γράφημα.
Ένας όρος, δίκτυο ροής , χρησιμοποιείται για να περιγράψει ένα δίκτυο κορυφών και άκρων με πηγή (S) και νεροχύτη (T). Κάθε κορυφή, εκτός από το S και το T , μπορεί να λάβει και να στείλει ίση ποσότητα υλικού μέσω αυτής. Το S μπορεί να στείλει μόνο και το T μπορεί να λάβει μόνο πράγματα.
Μπορούμε να απεικονίσουμε την κατανόηση του αλγορίθμου χρησιμοποιώντας μια ροή υγρού μέσα σε ένα δίκτυο σωλήνων διαφορετικής χωρητικότητας. Κάθε σωλήνας έχει μια ορισμένη χωρητικότητα υγρού που μπορεί να μεταφέρει σε μια περίπτωση. Για αυτόν τον αλγόριθμο, θα βρούμε πόση ποσότητα υγρού μπορεί να ρέει από την πηγή στο νεροχύτη σε μια περίπτωση χρησιμοποιώντας το δίκτυο.
Γράφημα δικτύου ροής
Χρησιμοποιούμενες ορολογίες
Διαδρομή επαύξησης
Είναι η διαδρομή που είναι διαθέσιμη σε ένα δίκτυο ροής.
Υπόλοιπο γράφημα
Αντιπροσωπεύει το δίκτυο ροής που έχει επιπλέον πιθανή ροή.
Υπολειμματική χωρητικότητα
Είναι η χωρητικότητα του άκρου μετά την αφαίρεση της ροής από τη μέγιστη χωρητικότητα.
Πώς λειτουργεί ο αλγόριθμος Ford-Fulkerson;
Ο αλγόριθμος ακολουθεί:
- Αρχικοποιήστε τη ροή σε όλες τις άκρες στο 0.
- Ενώ υπάρχει μια διαδρομή αύξησης μεταξύ της πηγής και του νεροχύτη, προσθέστε αυτήν τη διαδρομή στη ροή.
- Ενημερώστε το υπόλοιπο γράφημα.
Μπορούμε επίσης να εξετάσουμε το αντίστροφο μονοπάτι, εάν απαιτείται, διότι αν δεν το εξετάσουμε, ενδέχεται να μην βρούμε ποτέ τη μέγιστη ροή.
Οι παραπάνω έννοιες μπορούν να γίνουν κατανοητές με το παρακάτω παράδειγμα.
Παράδειγμα Ford-Fulkerson
Η ροή όλων των άκρων είναι 0 στην αρχή.
Παράδειγμα γραφήματος δικτύου ροής
- Επιλέξτε οποιαδήποτε αυθαίρετη διαδρομή από S έως T. Σε αυτό το βήμα, έχουμε επιλέξει τη διαδρομή SABT.
Εύρεση διαδρομής
Η ελάχιστη χωρητικότητα μεταξύ των τριών άκρων είναι 2 (BT). Με βάση αυτό, ενημερώστε τη ροή / χωρητικότητα για κάθε διαδρομή.
Ενημερώστε τις δυνατότητες - Επιλέξτε άλλη διαδρομή SDCT. Η ελάχιστη χωρητικότητα μεταξύ αυτών των άκρων είναι 3 (SD).
Εύρεση επόμενης διαδρομής
Ενημερώστε τις δυνατότητες σύμφωνα με αυτό.
Ενημερώστε τις δυνατότητες - Τώρα, ας εξετάσουμε επίσης την αντίστροφη διαδρομή BD. Επιλογή διαδρομής SABDCT. Η ελάχιστη υπολειμματική χωρητικότητα μεταξύ των άκρων είναι 1 (DC).
Βρείτε την επόμενη διαδρομή
Ενημέρωση των δυνατοτήτων.
Ενημέρωση χωρητικότητας
Η χωρητικότητα για διαδρομές προς τα εμπρός και προς τα πίσω εξετάζονται ξεχωριστά - Προσθήκη όλων των ροών = 2 + 3 + 1 = 6, που είναι η μέγιστη δυνατή ροή στο δίκτυο ροής.
Σημειώστε ότι εάν η χωρητικότητα για οποιοδήποτε άκρο είναι πλήρης, τότε δεν μπορεί να χρησιμοποιηθεί αυτή η διαδρομή.
Παραδείγματα Python, Java και 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
- Αγωγός διανομής νερού
- Πρόβλημα διμερούς αντιστοίχισης
- Κυκλοφορία με απαιτήσεις
