A Dinic-algoritmus a hálózatot szintekre bontja, és csak olyan éleket használ, amelyek egy szintből a következőbe vezetnek (szintgráf). Az algoritmus iteratívan építi a maximális áramlást az alábbi lépésekkel:
DinicAlgorithm(G, s, t):
max_flow = 0
amíg True:
# Szintgráf építése (BFS)
level = BFS(G, s, t)
ha level == -1:
térj vissza max_flow
# Blokkoló áramlás keresése (DFS)
while True:
flow = DFS(G, s, t, ∞, level)
ha flow == 0:
break
max_flow += flow
function BFS(G, s, t):
szintek = * len(G)
szintek = 0
sor =
amíg sor nem üres:
u = sor.pop(0)
minden v szomszédos u-val:
ha szintek == -1 és kapacitás(u, v) > 0:
szintek = szintek + 1
sor.append(v)
térj vissza szintek
function DFS(G, u, t, flow, level):
ha u == t:
térj vissza flow
minden v szomszédos u-val:
ha szint + 1 == szint és kapacitás(u, v) > 0:
min_flow = min(flow, kapacitás(u, v))
pushed = DFS(G, v, t, min_flow, level)
ha pushed > 0:
kapacitás(u, v) -= pushed
kapacitás(v, u) += pushed
térj vissza pushed
térj vissza 0
from collections import deque, defaultdict
class Dinic:
def __init__(self, n):
self.n = n
self.graph = defaultdict(list)
self.capacity = defaultdict(lambda: defaultdict(int))
def add_edge(self, u, v, cap):
self.graph.append(v)
self.graph.append(u)
self.capacity += cap # Több él esetén is összeadjuk a kapacitást
def bfs(self, s, t):
level = * self.n
level = 0
queue = deque()
while queue:
u = queue.popleft()
for v in self.graph:
if level == -1 and self.capacity > 0:
level = level + 1
queue.append(v)
return level
def dfs(self, u, t, flow, level, start):
if u == t:
return flow
while start < len(self.graph):
v = self.graph]
if level + 1 == level and self.capacity > 0:
min_cap = min(flow, self.capacity)
pushed = self.dfs(v, t, min_cap, level, start)
if pushed > 0:
self.capacity -= pushed
self.capacity += pushed
return pushed
start += 1
return 0
def max_flow(self, s, t):
total_flow = 0
while True:
level = self.bfs(s, t)
if level == -1:
break
start = * self.n
while True:
flow = self.dfs(s, t, float('inf'), level, start)
if flow == 0:
break
total_flow += flow
return total_flow
# Példa használat
n = 6 # csúcsok száma
dinic = Dinic(n)
dinic.add_edge(0, 1, 10)
dinic.add_edge(0, 2, 10)
dinic.add_edge(1, 2, 2)
dinic.add_edge(1, 3, 4)
dinic.add_edge(1, 4, 8)
dinic.add_edge(2, 4, 9)
dinic.add_edge(3, 5, 10)
dinic.add_edge(4, 5, 10)
print("Maximális áramlás:", dinic.max_flow(0, 5))
Kimenet:
Maximális áramlás: 19
A Dinic-algoritmus egy hatékony és széles körben alkalmazott módszer a maximális áramlás problémájának megoldására. Az iteratív szintgráf-alapú megközelítésével gyors és megbízható eredményt ad, különösen ritka gráfok esetén. Az algoritmus egyszerű logikája és optimalizált működése miatt népszerű választás a modern hálózatok és optimalizációs problémák megoldására.