Når man implementerer Prims algoritme kan det være lurt å hente ut den billigste kanten fra alle nodene du har tilgjengelig. Dette har jeg løst ved å legge alle kantene til alle tilgjengelige noder i en heap, og vil da hente ut den billigste kanten fra heapen hver gang. Men, hvordan kan jeg holde kontroll på hvor den kanten kommer fra når heapen automatisk sorterer alle kantene?

Basert på Piazza-spørsmål fra 2015

Ja, dette kan være litt tricky! Det er flere måter du kan gjøre det på. F.eks.:

  1. Du kan la hver node \(u\) ha en foreløpig forgjenger \(u.\pi\) (evt. lagret som \(\pi[u]\), i en hashtabell eller noe). Hver gang du justerer vekten/prioriteten til noden fordi du har funnet en ny og bedre vei via en kant \((v,u)\) så setter du \(u.\pi=v\) for å huske hvor du kom fra. (Det må du selvfølgelig også gjøre når du finner en sti i utgangspunktet, dvs., når du legger noden inn i køen til å begynne med.)

  2. Du kan legge inn informasjonen i køen. Sånn at du f.eks. kan la køen inneholde tupler som \((w,v,u)\), som betyr at du kan komme deg til \(u\) med kostnad \(w\) ved å gå via \(v\). Disse tuplene kan du sortere direkte. Det funker jo også om du legger inn samme node på nytt hver gang du finner en ny kant, og bare lar haugen ta seg av å velge minimum. Du må da ignorere noder du finner som du alt har besøkt.

Om du sjekker boka mi Python Algorithms så finner du en implementasjon:

def prim(G, s):
    P, Q = {}, [(0, None, s)]
    while Q:
        _, p, u = heappop(Q)
        if u in P: continue
        P[u] = p
        for v, w in G[u].items():
            heappush(Q, (w, u, v))
    return P

Her er G[u] altså en liste med naboer og tilhørende kantvekter.

Samme prinsipper gjelder også for Dijkstras algoritme, som vi kommer til siden. Eneste forskjell er egentlig at i stedet for at prioriteten er vekten til den korteste kanten vi kan nå noden via, så er vekten lik den korteste stien vi har funnet til noden fra starten.

Merk: Algoritmen Prim hos Cormen m. fl. baserer seg ikke på traversering som her, men legger alle noder inn i \(Q\) fra starten av.