Dalam tutorial ini, Anda akan mempelajari apa itu algoritma Ford-Fulkerson. Selain itu, Anda akan menemukan contoh kerja untuk menemukan aliran maksimum dalam jaringan aliran di C, C ++, Java dan Python.
Algoritma Ford-Fulkerson adalah pendekatan serakah untuk menghitung aliran maksimum yang mungkin dalam jaringan atau grafik.
Sebuah istilah, jaringan aliran , digunakan untuk menggambarkan jaringan simpul dan tepi dengan sumber (S) dan wastafel (T). Setiap simpul, kecuali S dan T , dapat menerima dan mengirim barang dalam jumlah yang sama melaluinya. S hanya bisa mengirim dan T hanya bisa menerima barang.
Kita dapat memvisualisasikan pemahaman algoritme menggunakan aliran cairan di dalam jaringan pipa dengan kapasitas berbeda. Setiap pipa memiliki kapasitas cairan tertentu yang dapat ditransfer secara instan. Untuk algoritme ini, kita akan menemukan berapa banyak cairan yang dapat dialirkan dari sumber ke wastafel pada suatu instance menggunakan jaringan.
Grafik jaringan aliran
Terminologi yang Digunakan
Augmenting Path
Ini adalah jalur yang tersedia di jaringan aliran.
Grafik Sisa
Ini mewakili jaringan aliran yang memiliki aliran tambahan yang mungkin.
Kapasitas Sisa
Ini adalah kapasitas tepi setelah mengurangi aliran dari kapasitas maksimum.
Bagaimana Algoritma Ford-Fulkerson bekerja?
Algoritme berikut:
- Inisialisasi aliran di semua sisi ke 0.
- Meskipun ada jalur augmentasi antara sumber dan sink, tambahkan jalur ini ke aliran.
- Perbarui grafik sisa.
Kami juga dapat mempertimbangkan jalur mundur jika diperlukan karena jika kami tidak mempertimbangkannya, kami mungkin tidak akan pernah menemukan aliran maksimum.
Konsep di atas dapat dipahami dengan contoh di bawah ini.
Contoh Ford-Fulkerson
Aliran semua sisi adalah 0 di awal.
Contoh grafik jaringan aliran
- Pilih sembarang jalur dari S ke T. Pada langkah ini, kami telah memilih jalur SABT.
Temukan jalur
Kapasitas minimum di antara ketiga sisi adalah 2 (BT). Berdasarkan ini, perbarui aliran / kapasitas untuk setiap jalur.
Perbarui kapasitas - Pilih jalur lain SDCT. Kapasitas minimum di antara tepi-tepi ini adalah 3 (SD).
Temukan jalur berikutnya
Perbarui kapasitas menurut ini.
Perbarui kapasitas - Sekarang, mari kita pertimbangkan juga BD jalur-terbalik. Memilih jalur SABDCT. Kapasitas residu minimum di antara edge-edge adalah 1 (DC).
Temukan jalur selanjutnya
Memperbarui kapasitas.
Perbarui kapasitas
Kapasitas untuk jalur maju dan mundur dianggap secara terpisah. - Menambahkan semua aliran = 2 + 3 + 1 = 6, yang merupakan aliran maksimum yang mungkin pada jaringan aliran.
Perhatikan bahwa jika kapasitas untuk setiap edge sudah penuh, maka jalur tersebut tidak dapat digunakan.
Contoh Python, Java dan C / C ++
Python Java 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; )
Aplikasi Ford-Fulkerson
- Pipa distribusi air
- Masalah pencocokan bipartit
- Sirkulasi dengan tuntutan
