I en tett (dense) graf, altså en graf med veldig mange kanter, vil man i Dijkstra gå over til en enklere datastruktur, og bruke en usortert liste som prioritetskø. Men for minimale spenntrær vil man da gjerne foretrekke Prim, som bruker vanskeligere datastrukturer enn Kruskal. Hvorfor?

Basert på et spørsmål fra 2019

Det er nyttig å trekke litt større linjer og lage seg mer overordnede «historier» om hvordan ting fungerer – men av og til stemmer de ikke helt overens med detaljene, og da kan det bli litt forvirrende. Her har du f.eks. laget en mental modell som knytter enkle vs. kompliserte datastrukturer opp mot spinkle (sparse) og tette (dense) grafer, og så ser du at det ikke stemmer helt. Da kan det være nyttig å dykke litt dypere.

Du har helt rett i at en tett vs. spinkel handler om antall kanter. Litt uformelt, for å si det med Cormen mfl., så er en spinkel graf en der $|E|$ er mye mindre enn $|V|^2$ (se s. 589). Akkurat hvor skillet går for når det lønner seg å bruke hvilken algoritme vil variere med problemstillingen.

Spørsmål 1: Hvorfor usortert liste vs. haug i Dijkstra for spinkle grafer?

Her har du forklart dette med at det er en enklere datastruktur, men det som er viktig her er kostnaden til ulike operasjoner. For en haug tar logaritmisk tid både å ta ut minimum og å endre en nøkkel.

I mange tilfeller vil dette være en god balanse. Operasjonene på både noder og kanter tar logaritmisk tid, og vi får kjøretid $O(E\lg V + V\lg V)$. Men om vi har mange flere kanter enn noder, så kan vi forskyve balansen. Vi kan gjøre operasjonen per kant billigere, på bekostning av operasjonen per node. Om vi bruker en usortert liste, kan vi oppdatere en kant i konstant tid, selv om det nå tar lineær tid å ta ut minimum. Men om vi har mange nok kanter i forhold til antall noder, så vil dette totalt sett lønne seg.

Dette har altså ikke noe med «enkelhet» å gjøre, egentlig, men med forholdet mellom kostnadene til operasjonene, og hvor mange vi gjør av hver.

Spørsmål 2: Hvorfor Prim vs. Kruskal for spinkle grafer?

Analogien din her er at Kruskal har en enklere datastruktur enn Prim. Det er jo ganske subjektivt; f.eks. er det å finne faktisk kjøretid på disjoint-forest-datastrukturen rimelig vanskelig :D

Dessuten har de samme asymptotiske kjøretid, $O(E\lg V)$, om du bruker en binærhaug, så her er ikke valget opplagt.

Jeg antar du tenker på bruken av Fibonacci-hauger, som jeg er enig i er atskillig mer komplisert enn binærhauger. Da får man en kjøretid $O(E + V\lg V)$, som er bedre enn $O(E\lg V + V\lg V)$ om man har minst $V$ kanter (eller deromkring). Altså bedre enn en binærhaug.

Men det er ingen motsetning her: Man får nemlig akkurat samme kjøretid ($O(E + V\lg V)$) i Dijkstras algoritme om man bruker Fibonacci-hauger. Og man får også samme kjøretid i Prim som i Dijkstra (dvs. $O(V^2)$) om man bruker en usortert liste. Kjøretidene til Prim og Dijkstra er i det hele tatt helt ekvivalente; de er jo i praksis samme algoritme, med ulik prioritet i prioritetskøen.

Så … det er ikke sikkert den mentale modellen din her ble noe forenklet nå, men kanskje noen detaljer likevel faller på plass?