Ford-Fulkersona algoritms

Satura rādītājs

Izmantotās terminoloģijas
Kā darbojas Ford-Fulkersona algoritms?
Ford-Fulkerson piemērs
Python, Java un C / C ++ piemēri
Ford-Fulkerson lietojumprogrammas

Šajā apmācībā jūs uzzināsiet, kas ir Ford-Fulkerson algoritms. Jūs atradīsit arī piemērus, kā atrast maksimālo plūsmu plūsmas tīklā C, C ++, Java un Python.

Ford-Fulkersona algoritms ir alkatīga pieeja, lai aprēķinātu maksimāli iespējamo plūsmu tīklā vai grafikā.

Termins plūsmas tīkls tiek izmantots, lai aprakstītu virsotņu un malu tīklu ar avotu (S) un izlietni (T). Katra virsotne, izņemot S un T , caur to var saņemt un nosūtīt vienādu daudzumu lietu. S var sūtīt tikai un T - tikai sīkumus.

Mēs varam vizualizēt izpratni par algoritmu, izmantojot šķidruma plūsmu dažādu jaudu cauruļu tīklā. Katrai caurulei ir noteikta šķidruma ietilpība, ko tā var pārnest instancē. Šim algoritmam mēs atradīsim, cik daudz šķidruma no avota var izplūst līdz izlietnei instancē, izmantojot tīklu.

Plūsmas tīkla diagramma

Izmantotās terminoloģijas

Palielināšanas ceļš

Tas ir plūsmas tīklā pieejamais ceļš.

Atlikušais grafiks

Tas attēlo plūsmas tīklu, kuram ir papildu iespējamā plūsma.

Atlikusī jauda

Tā ir malas ietilpība pēc plūsmas atņemšanas no maksimālās jaudas.

Kā darbojas Ford-Fulkersona algoritms?

Algoritms seko:

Inicializējiet plūsmu visās malās līdz 0.
Lai gan starp avotu un izlietni ir palielinošs ceļš, pievienojiet šo ceļu plūsmai.
Atjauniniet atlikušo grafiku.

Mēs varam apsvērt arī apgriezto ceļu, ja tas ir nepieciešams, jo, ja mēs tos neuzskatām, mēs nekad nevarēsim atrast maksimālu plūsmu.

Iepriekš minētos jēdzienus var saprast ar piemēru zemāk.

Ford-Fulkerson piemērs

Visu malu plūsma sākumā ir 0.

Plūsmas tīkla diagrammas piemērs

Atlasiet jebkuru patvaļīgu ceļu no S līdz T. Šajā solī esam izvēlējušies ceļu SABT. Atrodiet ceļu
Minimālā ietilpība starp trim malām ir 2 (BT). Pamatojoties uz to, atjauniniet katra ceļa plūsmu / jaudu. Atjauniniet jaudas
Atlasiet citu ceļu SDCT. Minimālā ietilpība starp šīm malām ir 3 (SD). Atrodiet nākamo ceļu
Atjauniniet jaudas atbilstoši tam. Atjauniniet jaudas
Tagad ņemsim vērā arī apgrieztā ceļa BD. Ceļa SABDCT atlase. Minimālā atlikusī jauda starp malām ir 1 (DC). Atrodiet nākamo ceļu
Jaudu atjaunināšana. Atjauniniet jaudas
Uz priekšu un atpakaļgaitas ceļu ietilpība tiek aplūkota atsevišķi.
Pievienojot visas plūsmas = 2 + 3 + 1 = 6, kas ir maksimālā iespējamā plūsma plūsmas tīklā.

Ņemiet vērā, ka, ja jebkuras malas ietilpība ir pilna, tad šo ceļu nevar izmantot.

Python, Java un C / C ++ piemēri

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; )