Parse the Ford-Fulkerson algorithm and implement it through Python

The Ford-Fulkerson algorithm is a greedy algorithm used to calculate the maximum flow in the network. The principle is to find an augmenting path with a positive remaining capacity. As long as the augmenting path is found, you can continue to add paths and calculate traffic. Until the augmenting path no longer exists, the maximum flow rate can be obtained.

Terminology of Ford-Fulkerson algorithm

Remaining capacity: It is the capacity minus the flow. In the Ford-Fulkerson algorithm, the remaining capacity is a positive number before it can continue to be used as a path.

Residual network: It is a network with the same vertices and edges, using residual capacity as capacity.

Augmented path: It is the path from the source point to the receiving point in the residual graph, with a final capacity of 0.

Ford-Fulkerson algorithm principle example

The concept may not be very clear. Let’s look at an example. The initial traffic of all edges of the flow network is 0, and there is a corresponding capacity upper limit. Set The starting point is S and the receiving point is T.

Path one, the remaining capacity of the S-A-B-T path is 8, 9, 2, and the minimum value is 2, so the traffic of path one is 2. At this time The network diagram has a flow rate of 2.

Path two, the remaining capacity of the S-D-C-T path is 3, 4, 5, and the minimum value is 3, so we can increase the traffic by 3. At this time The traffic of the network is 5.

Path three, the remaining capacity of the S-A-B-D-C-T path is 6, 7, 7, 1, 2, and the minimum value is 1, so the traffic increases by 1, which The network traffic at this time is 6.

At this point, there is no positive remaining capacity, and the maximum flow of the flow network is 6.

Python implements Ford-Fulkerson algorithm

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

The above is the detailed content of Parse the Ford-Fulkerson algorithm and implement it through Python. For more information, please follow other related articles on the PHP Chinese website!