WisFaq!

\require{AMSmath} geprint op maandag 20 september 2021

Dijkstra`s algoritme

Hoe volgt het dat Dijkstra's algorithme een runningtime van O(|V|2) heeft waar V het aantal knopen in de graaf is?

Vriendelijke groet,

Herman

herman de vries
27-1-2009

Antwoord

Als je het algoritme goed bestudeert zul je zien het ongeveer |V| iteraties kost waarin bij de i-de stap ongeveer |V|-i knopen doorlopen worden. Dit leidt tot de O(|V|2).

kphart
27-1-2009


© 2001-2021 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#58122 - Grafen - Student universiteit