Jeg lurer på om kjøretiden for Johnson når man bruker en binærhaug er \(O(V^2\lg V + VE\lg V)\). Eller er det \(O(VE\lg V)\) og i så fall hvorfor kan man fjerne det første leddet?

E-post-spørsmål fra 2018

Godt spørsmål! Svaret er ikke helt opplagt, dessverre – det er flere ting å ta tak i. Om vi ser bort fra noen detaljer, så består Johnson av én kjøring av Bellman-Ford etterfulgt av \(|V|\) kjøringer av Dijkstra. Den totale kjøretiden blir altså:

\[O(VE + V^2\lg V + VE\lg V)\]

Allerede her er vi inne på noen finurligheter, som ikke er helt innenfor pensum, men som er relativt rett fram: Slik Cormen m. fl. implementerer Dijkstra, bygger de prioritetskøen i starten. De sier der at de bruker \(|V|\) stk. Insert, som for en binærhaug vil gi en byggetid på \(O(V\lg V)\) – om vi i stedet bare bruke Build-Heap, så blir kjøretiden \(O(V)\). Men vi kan gå lenger enn det: Heller enn å bygge hele haugen til å begynne med, kan vi la grafen være urørt fra starten av, og bare legge inn noder i \(Q\) etterhvert som de oppdages, akkurat som i traverseringsalgoritmer som f.eks. BFS. I så fall vil vi ha én Insert og én Extract for hver node vi besøker, men vi besøker jo bare noder vi kan nå frem til – og vi kan bare nå frem til \(O(E)\).

Så om vi implementerer Dijkstra slik, så ender vi med:

\[O(VE + VE\lg V + VE\lg V)\]

Med andre ord, \(O(VE\lg V)\). Men hva om vi implementerer algoritmen slik Cormen m. fl. gjør det, så vi får den forenklede kjøretiden

\[O(V^2\lg V + VE\lg V)\]

Kan vi likevel kvitte oss med \(V^2\lg V\)-leddet? I beskrivelsen av Dijkstra skriver de:

The total running time is therefore \(O((V + E)\lg V)\), which is \(O(E\lg V)\) if all vertices are reachable from the source.

I dette tilfellet vil også traverseringsvarianten jeg beskrev over nå frem til alle nodene, så resonnementet blir da det samme. Så om vi gjør en antagelse om f.eks. at det finnes minst én node som kan nå alle andre så vil kjøretiden til Johnson være \(O(VE\lg V)\). Men Cormen m. fl. gjør (etter det jeg kan se) ikke den antagelsen eksplisitt – de skriver bare:

The … binary heap implementation yields a running time of \(O(VE\lg V)\), which is still asymptotically faster than the Floyd-Warshall algorithm if the graph is sparse.

Men med mindre man vet at \(|V|=O(E)\) og dermed \(|V|^2=O(VE)\), så er jo ikke det sikkert! Det er jo et spesielt relevant spørsmål når vi jobber med glisne (sparse) grafer – som de omtaler det:

sparse graphs—those for which \(\vert E\vert\) is much less than \(\vert V^2\vert\)

Da er det jo ikke urimelig å tenke at kanskje \(|E|<|V|\), og i så fall vil jo kjøretiden måtte forenkles til \(O(V^2\lg V)\), med implementasjonen til Cormen et al. Så om du blir spurt om hva kjøretiden til Johnson er, så er nok det tryggeste svaret \(O(V^2\lg V + VE\lg V)\), men \(O(VE\lg V)\) er også et rimelig svar – spesielt siden det er det som står i boka! Vi baserer oss da på den samme antagelsen som gir oss denne forenklingen for Dijkstra, nemlig at vi kan nå alle nodene (fra minst én av startnodene).