Login using mooc.fi
—
Dark mode
Tietorakenteet ja algoritmit kevät 2023
Dijkstran algoritmi
Task
CSES - Dijkstran algoritmi
Toteuta kurssikirjan mukainen Dijkstran algoritmi ja testaa sen toimintaa suunnatussa verkossa, joka on muodostettu seuraavasti:
Verkossa on solmut $1,2,\dots,N$ ja $N=5000$.
Aloitussolmu on solmu $1$.
Solmusta $a$ on kaari solmuun $b$, jos $a<b$ ja $b-a<10$.
Jokaisen kaaren paino on satunnainen kokonaisluku välillä $1 \dots 1000$.
Kaaret ovat satunnaisessa järjestyksessä vieruslistoissa.
Kauanko algoritmin suoritus vie aikaa?
s
Testissä käyttämäsi koodi:
Viikko 11
Bellman–Ford-algoritmi
Dijkstran algoritmi
Paras reitti
Välimatkat
Listahyppy
Seinäpoisto
Lyhennys
Veden mittaus