Dinic-algoritmus
Kiejtés
- IPA: [ ˈdinit͡sɒlɡoritmuʃ]
Főnév
- (matematika, algoritmusok) A Dinic-algoritmus egy hatékony megoldás a maximális áramlás problémájára irányított, kapacitással ellátott hálózatokban. Az algoritmust Eugene A. Dinic dolgozta ki 1970-ben, és az Edmonds-Karp-algoritmus optimalizált változata. Az algoritmus időbonyolultsága (O(V^2E)), de speciális esetekben (például egységkapacitású hálózatok) lineárisabb, (O(E ))-re csökkenthető.
Probléma meghatározása
Bemenet:
- Egy irányított gráf (G = (V, E)), ahol:
- (V) a csúcsok halmaza.
- (E) az élek halmaza.
- Minden élhez tartozik egy kapacitás (c(u, v)).
- Egy forrás ((s)) és egy nyelő ((t)) csúcs.
Kimenet:
- A maximális áramlás értéke, amely (s)-ből (t)-be jut a hálózatban.
Fő ötlet
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:
Algoritmus működése
1. Szintgráf építése (BFS)
- Használj szélességi keresést ((BFS)), hogy meghatározd a szinteket, ahol minden csúcs szintje az (s)-től való távolság.
- Ha (t) nem érhető el, az algoritmus leáll, mert elérte a maximális áramlást.
2. Blokkoló áramlás keresése (DFS)
- Mélységi keresést ((DFS)) használsz, hogy megtaláld a blokkoló áramlást, amely nem hagy ki egyetlen potenciális utat sem a szintgráfban.
3. Áramlás frissítése
- A blokkoló áramlást hozzáadod a meglévő áramláshoz, majd frissíted a reziduális gráfot.
4. Ismétlés
- Új szintgráfot hozol létre, és megismétled a folyamatot, amíg nincs több blokkoló áramlás.
Időbonyolultság
- Általános eset: (O(V^2E)), ahol (V) a csúcsok száma, (E) az élek száma.
- Egységkapacitású hálózat: (O(E )).
Pszeudokód
DinicAlgorithm(G, s, t):
max_flow = 0
amíg True:
# Szintgráf építése (BFS)
level = BFS(G, s, t)
ha level[t] == -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 = [-1] * len(G)
szintek[s] = 0
sor = [s]
amíg sor nem üres:
u = sor.pop(0)
minden v szomszédos u-val:
ha szintek[v] == -1 és kapacitás(u, v) > 0:
szintek[v] = szintek[u] + 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[u] + 1 == szint[v] é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
Python implementáció
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[u].append(v)
self.graph[v].append(u)
self.capacity[u][v] += cap # Több él esetén is összeadjuk a kapacitást
def bfs(self, s, t):
level = [-1] * self.n
level[s] = 0
queue = deque([s])
while queue:
u = queue.popleft()
for v in self.graph[u]:
if level[v] == -1 and self.capacity[u][v] > 0:
level[v] = level[u] + 1
queue.append(v)
return level
def dfs(self, u, t, flow, level, start):
if u == t:
return flow
while start[u] < len(self.graph[u]):
v = self.graph[u][start[u]]
if level[u] + 1 == level[v] and self.capacity[u][v] > 0:
min_cap = min(flow, self.capacity[u][v])
pushed = self.dfs(v, t, min_cap, level, start)
if pushed > 0:
self.capacity[u][v] -= pushed
self.capacity[v][u] += pushed
return pushed
start[u] += 1
return 0
def max_flow(self, s, t):
total_flow = 0
while True:
level = self.bfs(s, t)
if level[t] == -1:
break
start = [0] * 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
Előnyök
- Hatékonyság:
- Az iteratív szintgráf-építés és blokkoló áramlás gyorsítja az algoritmust.
- Skálázhatóság:
- Nagy és ritka gráfok esetén is hatékony.
- Egyszerűség:
- Bár bonyolultnak tűnik, az implementáció logikusan felépíthető.
Hátrányok
- Memóriaigény:
- Nagy gráfok esetén jelentős memóriát igényel a reziduális gráf tárolása.
- Speciális esetek:
- Nagyon sűrű gráfoknál nem biztos, hogy gyorsabb, mint más algoritmusok (pl. Edmonds-Karp).
Alkalmazások
- Hálózati optimalizáció:
- Adatátvitel optimalizálása számítógépes hálózatokon.
- Logisztikai problémák:
- Maximális árufolyam tervezése.
- Áramkörök:
- Elektromos áram optimalizálása.
- Játékok:
- Győzelmi stratégiák számítása gráfreprezentált problémákban.
Összegzés
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.
- Dinic-algoritmus - Értelmező szótár (MEK)
- Dinic-algoritmus - Etimológiai szótár (UMIL)
- Dinic-algoritmus - Szótár.net (hu-hu)
- Dinic-algoritmus - DeepL (hu-de)
- Dinic-algoritmus - Яндекс (hu-ru)
- Dinic-algoritmus - Google (hu-en)
- Dinic-algoritmus - Helyesírási szótár (MTA)
- Dinic-algoritmus - Wikidata
- Dinic-algoritmus - Wikipédia (magyar)