Algoritma Ford-Fulkerson

Dalam tutorial ini, anda akan mengetahui apa itu algoritma Ford-Fulkerson. Anda juga akan mendapat contoh kerja untuk mencari aliran maksimum dalam rangkaian aliran di C, C ++, Java dan Python.

Algoritma Ford-Fulkerson adalah pendekatan tamak untuk mengira aliran maksimum yang mungkin dalam rangkaian atau grafik.

Istilah, rangkaian aliran , digunakan untuk menggambarkan rangkaian bucu dan tepi dengan sumber (S) dan sink (T). Setiap bucu, kecuali S dan T , dapat menerima dan mengirim jumlah barang yang sama melaluinya. S hanya boleh menghantar dan T hanya dapat menerima barang.

Kita dapat memvisualisasikan pemahaman algoritma menggunakan aliran cecair di dalam rangkaian paip dengan kapasiti yang berbeza. Setiap paip mempunyai kapasiti cecair tertentu yang dapat dipindahkan pada satu ketika. Untuk algoritma ini, kita akan mencari berapa banyak cecair yang dapat dialirkan dari sumber ke sink pada satu ketika menggunakan rangkaian.

Graf rangkaian aliran

Terminologi Digunakan

Jalan Peningkatan

Ini adalah jalan yang tersedia dalam rangkaian aliran.

Graf Sisa

Ini mewakili rangkaian aliran yang mempunyai kemungkinan aliran tambahan.

Kapasiti Sisa

Ini adalah kapasiti tepi setelah mengurangkan aliran dari kapasiti maksimum.

Bagaimana Algoritma Ford-Fulkerson berfungsi?

Algoritma berikut:

  1. Memulakan aliran di semua tepi ke 0.
  2. Walaupun terdapat jalan peningkatan antara sumber dan sink, tambahkan jalan ini ke aliran.
  3. Kemas kini baki grafik.

Kita juga boleh mempertimbangkan jalan balik jika diperlukan kerana jika kita tidak mempertimbangkannya, kita mungkin tidak akan pernah menemui aliran maksimum.

Konsep di atas dapat difahami dengan contoh di bawah.

Contoh Ford-Fulkerson

Aliran semua tepi adalah 0 pada awalnya.

Contoh grafik rangkaian aliran
  1. Pilih mana-mana jalan sewenang-wenangnya dari S ke T. Dalam langkah ini, kami telah memilih jalan SABT. Cari jalan
    Kapasiti minimum di antara tiga tepi ialah 2 (BT). Berdasarkan ini, kemas kini aliran / kapasiti untuk setiap jalan. Kemas kini kapasiti
  2. Pilih jalan lain SDCT. Kapasiti minimum di antara tepi ini ialah 3 (SD). Cari jalan seterusnya
    Kemas kini kapasiti mengikut ini. Kemas kini kapasiti
  3. Sekarang, marilah kita mempertimbangkan BD jalan balik juga. Memilih jalan SABDCT. Kapasiti baki minimum di antara tepinya ialah 1 (DC). Cari jalan seterusnya
    Mengemas kini kapasiti. Kemas kini kapasiti
    Kapasiti untuk laluan maju dan mundur dipertimbangkan secara berasingan.
  4. Menambah semua aliran = 2 + 3 + 1 = 6, yang merupakan aliran maksimum pada rangkaian aliran.

Perhatikan bahawa jika kapasiti pinggir mana pun penuh, maka jalan itu tidak dapat digunakan.

Contoh Python, Java dan 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; )

Aplikasi Ford-Fulkerson

  • Saluran penyaluran air
  • Masalah pemadanan bipartit
  • Peredaran dengan tuntutan

Artikel menarik...