Menghuraikan algoritma Ford-Fulkerson dan melaksanakannya melalui Python

Algoritma Ford-Fulkerson ialah algoritma tamak yang digunakan untuk mengira trafik maksimum dalam rangkaian. Prinsipnya adalah untuk mencari laluan penambahan dengan kapasiti baki positif Selagi laluan penambahan ditemui, anda boleh terus menambah laluan dan mengira trafik. Sehingga laluan penambahan tidak lagi wujud, kadar aliran maksimum boleh diperolehi.

Terminologi algoritma Ford-Fulkerson

Baki kapasiti: Ia adalah kapasiti tolak aliran Dalam algoritma Ford-Fulkerson, baki kapasiti ialah nombor positif sebelum ia boleh terus menjadi laluan.

Rangkaian sisa: Ia adalah rangkaian dengan bucu dan tepi yang sama, menggunakan kapasiti baki sebagai kapasiti.

Laluan tambahan: Ia ialah laluan dari titik sumber ke titik penerimaan dalam graf baki, dengan kapasiti akhir 0.

Contoh prinsip algoritma Ford-Fulkerson

Konsepnya mungkin tidak begitu jelas Mari kita lihat contoh Trafik awal semua tepi rangkaian aliran ialah 0, dan terdapat had kapasiti atas yang sepadan menjadi S dan titik penerimaan ialah T. .

Laluan satu, baki kapasiti laluan S-A-B-T ialah 8, 9, 2, dan nilai minimum ialah 2, jadi trafik laluan satu ialah 2, dan trafik rajah rangkaian ialah 2.

Laluan dua, baki kapasiti laluan S-D-C-T ialah 3, 4, 5, dan nilai minimum ialah 3, jadi kita boleh meningkatkan trafik sebanyak 3, dan trafik rangkaian ialah 5.

Laluan tiga, baki kapasiti laluan S-A-B-D-C-T ialah 6, 7, 7, 1, 2, dan nilai minimum ialah 1, jadi trafik meningkat sebanyak 1, dan trafik rangkaian ialah 6.

Pada ketika ini, tiada kapasiti baki positif, dan aliran maksimum rangkaian aliran ini ialah 6.

Python melaksanakan algoritma 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))

Atas ialah kandungan terperinci Menghuraikan algoritma Ford-Fulkerson dan melaksanakannya melalui Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!