bellman-ford.md

Bellman-Ford

Bellman-Ford algoritmen løser single-source shortest-path (SSSP) problemet i det generelle tilfellet hvor kanter kan ha negativ vekt.

Den formelle definisjonen av det generelle problemet

Tilleggskrav for korrekthet

Trinn for trinn

Gitt en vektet rettet graf $G=(V,E)$ med kilde $s$ og en vektfunksjon $w : E -> \mathbb{R}$, vil Bellman-Ford returnere True hvis og bare hvis grafens startnode ikke finner noen ingen negativ-vekt sykler.

G = graf | w = vekting | i = teller | u = fra-node | v = til-node

Bellman-Ford(G,w,s)
1 Initialize-Single-Source(G,s)
2 for i=1 to |G.V| - 1
3   for each edge (u.v) ∈ G.E
4     Relax(u,v,w)
5 for each edge (u.v) ∈ G.Ez
6   if v.d > u.d + w (u,v)
7     return False
8 return True

1: Avstand = uendelig, forgjengernoder = NIL, startnode avstand = 0 2: Tell opp til V-1 ganger

3-4: For hver kant, slakk kanten

5-6: Er første del av relax!

7: Dersom kanten ikke ble slakket helt etter 4, returner false. Det betyr at det er en negativ sykel i grafen!

8: Hvis alle var korrekt slakket, returner true. Algoritmen fungerte!

Korrekthetsbevis

Korrekthetsbevis for Bellman-Ford er på side 653 i pensumboka.

Styrker og svakheter sammenlignet med andre

+ Kan oppdage negative sykler
- Høyere kjøretid enn Dijkstras algoritme

Kjøretid og utregning

Operasjon	Antall	Kjøretid
Initialisering	1	$\Theta(V)$
RELAX	V-1	$\Theta(E)$
RELAX	1	$O(E)$

Operasjon	Antall	Kjøretid
Initialisering	$1$	$\Theta(V)$
Relax	$V-1$	$\Theta(1)$
Relax	$O(V)$	$\Theta(1)$

1. Slakker hver kant $|V|-1$ ganger, $O(E)$.
2. Initalisering $O(V)$
3. Total kjøretid på $O(V\cdot E)$.

Python kodeeksempel