— Dark mode

Tietorakenteet ja algoritmit kevät 2023

Dijkstran algoritmi

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-algoritmiDijkstran algoritmiParas reittiVälimatkatListahyppySeinäpoistoLyhennysVeden mittaus