Analyser l'algorithme Ford-Fulkerson et l'implémenter via Python

L'algorithme Ford-Fulkerson est un algorithme glouton utilisé pour calculer le trafic maximum sur le réseau. Le principe est de trouver un chemin augmentant avec une capacité restante positive. Tant que le chemin augmentant est trouvé, vous pouvez continuer à ajouter des chemins et à calculer le trafic. Jusqu'à ce que le chemin d'augmentation n'existe plus, le débit maximum peut être obtenu.

Terminologie de l'algorithme de Ford-Fulkerson

Capacité restante : c'est la capacité moins le flux. Dans l'algorithme de Ford-Fulkerson, la capacité restante est un nombre positif avant de pouvoir continuer à être un chemin.

Réseau résiduel : C'est un réseau avec les mêmes sommets et arêtes, utilisant la capacité résiduelle comme capacité.

Chemin augmenté : C'est le chemin du point source au point récepteur dans le graphe résiduel, avec une capacité finale de 0.

Exemple de principe de l'algorithme Ford-Fulkerson

Le concept n'est peut-être pas très clair. Regardons un exemple. Le trafic initial de tous les bords du réseau de flux est de 0, et il existe une limite de capacité supérieure correspondante. être S et le point de réception être T. .

Chemin un, la capacité restante du chemin S-A-B-T est de 8, 9, 2 et la valeur minimale est de 2, donc le trafic du chemin un est de 2 et le trafic du diagramme de réseau est de 2.

Chemin deux, la capacité restante du chemin S-D-C-T est de 3, 4, 5 et la valeur minimale est de 3, nous pouvons donc augmenter le trafic de 3 et le trafic réseau est de 5.

Chemin trois, la capacité restante du chemin S-A-B-D-C-T est de 6, 7, 7, 1, 2 et la valeur minimale est de 1, donc le trafic augmente de 1 et le trafic réseau est de 6.

A ce stade, il n'y a pas de capacité restante positive, et le débit maximum de ce réseau de flux est de 6.

Python implémente l'algorithme de Ford-Fulkerson

from collections import defaultdict

class Graph:

    def __init__(self, graph):
        self.graph = graph
        self. ROW = len(graph)

    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

    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]

            max_flow += path_flow

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!