Algorithme de Ford-Fulkerson

Table des matières

Terminologies utilisées
Comment fonctionne l'algorithme Ford-Fulkerson?
Exemple Ford-Fulkerson
Exemples Python, Java et C / C ++
Applications Ford-Fulkerson

Dans ce didacticiel, vous apprendrez ce qu'est l'algorithme de Ford-Fulkerson. Vous trouverez également des exemples pratiques de recherche de flux maximal dans un réseau de flux en C, C ++, Java et Python.

L'algorithme de Ford-Fulkerson est une approche gourmande pour calculer le débit maximum possible dans un réseau ou un graphe.

Un terme, réseau de flux , est utilisé pour décrire un réseau de sommets et d'arêtes avec une source (S) et un puits (T). Chaque sommet, à l'exception de S et T , peut recevoir et envoyer une quantité égale de choses à travers lui. S peut uniquement envoyer et T ne peut recevoir que des données.

Nous pouvons visualiser la compréhension de l'algorithme à l'aide d'un flux de liquide à l'intérieur d'un réseau de tuyaux de différentes capacités. Chaque tuyau a une certaine capacité de liquide qu'il peut transférer à une instance. Pour cet algorithme, nous allons trouver la quantité de liquide qui peut s'écouler de la source vers le puits au niveau d'une instance utilisant le réseau.

Graphique du réseau de flux

Terminologies utilisées

Augmenter le chemin

C'est le chemin disponible dans un réseau de flux.

Graphique résiduel

Il représente le réseau de flux qui a un flux supplémentaire possible.

Capacité résiduelle

C'est la capacité du bord après soustraction du débit de la capacité maximale.

Comment fonctionne l'algorithme Ford-Fulkerson?

L'algorithme suit:

Initialisez le flux dans toutes les arêtes à 0.
S'il existe un chemin d'augmentation entre la source et le collecteur, ajoutez ce chemin au flux.
Mettez à jour le graphique résiduel.

Nous pouvons également envisager des chemins inversés si nécessaire car si nous ne les considérons pas, nous ne trouverons peut-être jamais un débit maximum.

Les concepts ci-dessus peuvent être compris avec l'exemple ci-dessous.

Exemple Ford-Fulkerson

Le flux de toutes les arêtes est égal à 0 au début.

Exemple de graphique de réseau de flux

Sélectionnez n'importe quel chemin arbitraire de S à T. Dans cette étape, nous avons sélectionné le chemin SABT. Trouver un chemin
La capacité minimale entre les trois arêtes est de 2 (BT). Sur cette base, mettez à jour le débit / la capacité de chaque chemin. Mettre à jour les capacités
Sélectionnez un autre chemin SDCT. La capacité minimale entre ces bords est de 3 (SD). Trouver le chemin suivant
Mettez à jour les capacités en fonction de cela. Mettre à jour les capacités
Maintenant, considérons également le chemin inverse BD. Sélection du chemin SABDCT. La capacité résiduelle minimale entre les bords est de 1 (DC). Trouver le chemin suivant
Mise à jour des capacités. Mettre à jour les capacités
La capacité des trajets aller et retour est considérée séparément.
En ajoutant tous les flux = 2 + 3 + 1 = 6, qui est le débit maximum possible sur le réseau de flux.

Notez que si la capacité d'un tronçon est pleine, ce chemin ne peut pas être utilisé.

Exemples Python, Java et 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; )