Vi begynner med å anta en asyklisk graf. Vi ser at vi kan la grafen være sin egen delinstansgraf.
Vil finne avstand $\delta(s, t)$ fra startnoden $s$. Vi antar så induktivt at vi har funnet $\delta(s, -)$ for inn-naboer. Inn-nabo $x$ gir mulig stilengde $\delta(s, x) + w(x, t)$; velg minium!
Vi får altså at $\delta(s, t) = min\{\delta(s, u) + w(u, t), \delta(s, v) + w(v, t)\}$
Video startet;
Dekomponeringen fungerer bare for asykliske grafer!
topologically sort G
initialize_single_source(G, s)
for each vertex v in V
for each edge (u, v) in E
relax(u, v, w)
end
end
function initialize_single_source(G, s)
for each vertex v in V
v.d = Inf
v.pi = nothing
end
s.d = 0
end
function relax(u, v, w)
if v.d > u.d + w(u, v)
v.d = u.d + w(u, v)
v.pi = u
end
end
Vil heller bruker ut kanter enn inn kanter.
Hvis vi skiller ut init, kanv i kjøre minium
Så lenge u.d er rett, kan vi trygt utføre linje 8 og 9 (de siste to linjene)
Med andre ord, nå kan vi bruke ut-kanter også!
Dette kalles reaching, istedenfor pulling. Som i vanlig DP, husk valg som tas. Dette gjøres vha. en forgjenger ($\pi$)!
Flytter init og min til en egen funksjon, refaktor!
function dag_shortest_path(G, w, s)
topologically sort the vertices of G
initialize-single-source(G, s)
for each vertex u, in topsort order
for each vertex v in G.adj[u]
relax(u, v, w)
end
end
end
NB! Sykler fungerer ikke med denne modellen
| Operasjon | Antall | Kjøretid |
|---|---|---|
| Topologisk-sortering | 1 | $\Theta(V + E)$ |
| Initialisering | 1 | $\Theta(V)$ |
| RELAX | E | $\Theta(1)$ |
Kantslakking er altså en oppspalting av miniums-operasjoner fra dekomponeringen. Vi har foreløpig ikke vært så kreative med hvordan vi har brukt det - la oss studere teknikken i litt mer detalj.
Kantslakking; problematisk når vi har flere strukne kanter i en sti.
Om p er en kortest vei fra s til v og vi slakker kantene til p i rekkefølge, så vil v få riktig avstandsestimat. Det gjelder uavhengig av om andre slakkinger forekommer, selv om de kommer innimellom. Se side 650 for flere slektninger av denne egenskapen.
La $\langle v_1, v_2, \ldots , v_k\rangle$ være korteste vei til $z$. Vi vil slakke kantene langs stien, men kjenner ikke rekkefølgen.
Løsning: Slakk absolutt alle kanter $k - 1$ ganger!
Hvis vi lar $k = |V|$ så får alle noder rett estimat
function bellman_ford(G, w, s)
initialize_single_source(G, s)
for i = 1 to |G.V| - 1
for each edge (u, v) in G.E
relax(u, v w)
end
end
for each edge (u, v) in G.E
if v.d > u.d + w(u, v)
return false
end
end
return true
| Operasjon | Antall | Kjøretid |
|---|---|---|
| Initialisering | 1 | $\Theta(V)$ |
| RELAX | $V - 1$ | $\Theta(E)$ |
| RELAX | $O(V)$ | $\Theta(E)$ |
Totalt: O(VE)
Om et estimat endres, så var tidligere slakking fra noden bortkastet.
Konklusjon: Slakk kanter fra v når v.d ikke kan forbedres.
Slakk kanter ut fra noder i topologisk sortert rekkefølge
Når alle inn-kanter er slakket kan ikke noden forbedres og trygt velges som neste.
Velg den gjenværende med lavest estimat.
Gjenværende noder kan kun forbedres ved slakking fra andre gjenværende. Det laveste estimatet kan dermed ikke forbedres.
function dijkstra(G, w, s)
initialize_single_source(G, s)
S = []
Q. = G.V #Queue
while Q != empty
u = extract_min(Q) # Korteste stien til start
push!(S, u)
for each vertex v in G.adj[u]
relax(u, v, w)
end
end
end
| Operasjon | Antall | Kjøretid |
|---|---|---|
| Initialisering | 1 | $\Theta(V)$ |
| BUILD-HEAP | 1 | $\Theta(V)$ |
| EXTRACT-MIN | $V$ | $O(lg V)$ |
| DECREASE-KEY | $E$ | $O(lg V)$ |
Total: O(V lg V + E lg V)
Med binærheap: bedre enn lineært søk for $E = o(V^2/lg V)$
Med Fibonacci-heap: DECREASE-KEY er $O(1)$: vi får $O(V lg V + E)$