Analysieren Sie den Ford-Fulkerson-Algorithmus und implementieren Sie ihn über Python

Der Ford-Fulkerson-Algorithmus ist ein gieriger Algorithmus, der zur Berechnung des maximalen Datenverkehrs im Netzwerk verwendet wird. Das Prinzip besteht darin, einen Erweiterungspfad mit einer positiven Restkapazität zu finden. Solange der Erweiterungspfad gefunden wird, können Sie weiterhin Pfade hinzufügen und den Verkehr berechnen. Bis der Verstärkungspfad nicht mehr vorhanden ist, kann die maximale Durchflussrate erreicht werden.

Terminologie des Ford-Fulkerson-Algorithmus

Restkapazität: Es handelt sich um die Kapazität abzüglich des Durchflusses. Im Ford-Fulkerson-Algorithmus ist die verbleibende Kapazität eine positive Zahl, bevor sie weiterhin ein Pfad sein kann.

Restnetzwerk: Es handelt sich um ein Netzwerk mit denselben Scheitelpunkten und Kanten, das die Restkapazität als Kapazität verwendet.

Erweiterter Pfad: Dies ist der Pfad vom Quellpunkt zum Empfangspunkt im Restdiagramm mit einer Endkapazität von 0.

Beispiel für das Prinzip des Ford-Fulkerson-Algorithmus

Das Konzept ist möglicherweise nicht sehr klar. Schauen wir uns ein Beispiel an. Der anfängliche Verkehr an allen Kanten des Flussnetzwerks ist 0, und es gibt eine entsprechende obere Kapazitätsgrenze sei S und der Empfangspunkt sei T. .

Pfad eins, die verbleibende Kapazität des S-A-B-T-Pfads beträgt 8, 9, 2 und der Mindestwert beträgt 2, sodass der Verkehr von Pfad eins 2 und der Verkehr des Netzwerkdiagramms 2 beträgt.

Pfad zwei, die verbleibende Kapazität des S-D-C-T-Pfads beträgt 3, 4, 5 und der Mindestwert beträgt 3, sodass wir den Datenverkehr um 3 erhöhen können und der Netzwerkverkehr 5 beträgt.

Pfad drei, die verbleibende Kapazität des S-A-B-D-C-T-Pfads beträgt 6, 7, 7, 1, 2 und der Mindestwert ist 1, sodass der Datenverkehr um 1 steigt und der Netzwerkverkehr 6 beträgt.

Zu diesem Zeitpunkt gibt es keine positive Restkapazität und der maximale Durchfluss dieses Durchflussnetzwerks beträgt 6.

Python implementiert den Ford-Fulkerson-Algorithmus

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

Das obige ist der detaillierte Inhalt vonAnalysieren Sie den Ford-Fulkerson-Algorithmus und implementieren Sie ihn über Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!