Hei, hvordan optimaliserer man didjikstras algoritme mest mulig. Jeg er klar over at man bør bruke heap og node liste, men til dette har jeg noen spørsmål.

Jeg har vanligvis brukt binær heap når jeg programmerer, men er andre heap som fibonacci heap kjappere?

Når man lager heap fra bunnen av, hva kan man gjøre for å sørge for at den går så rask som mulig?

Går det an å kombinere knapsack med graf teori?

Ja, her har du en oversikt over kompleksiteten til ulike operasjon i ulike heap-varianter.

Så lenge kompleksitenet på de operasjonene som lager heapen er så god/lav som mulig, så trenger du ikke gjøre noe spesielt. Bruker du en Fibonacci heap er innsetting O(1), og konstruksjon av en heap på størrelse n blir O(n).

Fibonacci heap gir forbedra kjøretid for en glissen graf, dvs hvis du har færre enn O(V^2) kanter. Kan også bruke f.eks. nabomatrise. Optimalisering av algoritmer går ofte på hvilket undercase du har og hvilken datastruktur som er fordelaktig, men generelt sett er vel beste generelle Dijkstra O(E + VlgV) for fibheap, noe som er bedre enn den vanlige O(ElgV VlgV).