Ford-Fulkerson 알고리즘을 구문 분석하고 Python을 통해 구현합니다.

Ford-Fulkerson 알고리즘은 네트워크의 최대 트래픽을 계산하는 데 사용되는 그리디 알고리즘입니다. 원칙은 남은 용량이 양수인 증가 경로를 찾는 것입니다. 증가 경로가 발견되는 한 계속해서 경로를 추가하고 트래픽을 계산할 수 있습니다. 증가 경로가 더 이상 존재하지 않을 때까지 최대 유량을 얻을 수 있습니다.

Ford-Fulkerson 알고리즘 용어

남은 용량: 용량에서 흐름을 뺀 값입니다. Ford-Fulkerson 알고리즘에서 남은 용량은 계속 경로가 될 수 있기 전의 양수입니다.

잔여 네트워크: 잔여 용량을 용량으로 사용하는 정점과 가장자리가 동일한 네트워크입니다.

증강 경로: 잔여 그래프의 소스 ​​지점에서 수신 지점까지의 경로이며 최종 용량은 0입니다.

Ford-Fulkerson 알고리즘 원리 예

예를 들어 보면 흐름 네트워크의 모든 가장자리의 초기 트래픽이 0이고 해당하는 최대 용량 제한이 있습니다. S이고 수신 지점은 T입니다.

경로 1, S-A-B-T 경로의 남은 용량은 8, 9, 2이고 최소값은 2이므로 경로 1의 트래픽은 2, 네트워크 다이어그램의 트래픽은 2입니다.

경로 2, S-D-C-T 경로의 남은 용량은 3, 4, 5이고 최소값은 3이므로 트래픽을 3씩 늘릴 수 있고 네트워크 트래픽은 5입니다.

Path 3, S-A-B-D-C-T 경로의 남은 용량은 6, 7, 7, 1, 2이고 최소값은 1이므로 트래픽이 1씩 증가하고 네트워크 트래픽은 6이 됩니다.

이 시점에서 긍정적인 잔여 용량은 없으며 이 흐름 네트워크의 최대 흐름은 6입니다.

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

위 내용은 Ford-Fulkerson 알고리즘을 구문 분석하고 Python을 통해 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!