Lyhyimpien reittien etsiminen muuttuvassa graafissa - Kauko, Ilari (2020)
Tämän tutkimuksen tarkoitus on selvittää, miten kannattaa käytännössä etsiä lyhyimpiä reittejä suuntaamattomassa graafissa, joka muuttuu vähitellen etsintöjen väleissä. Tutkielman konteksti on luoda todentuntuisia, suunnittelemattomalta vaikuttavia katuverkkoja graafin mallintamaan ympäristöön. Katuverkko helpottaa olennaisesti kulkua paikoista toisiin ja se muodostuu vähitellen, joten graafin muuttuminen on tarkemmin ainoastaan kaarten pituuksien pienenemistä. Käsiteltäviä algoritmeja lyhyimmän reitin etsimiseen ovat Dijkstra, sen laajennokset ja ainakin teoriassa kilpailukykyinen niin kutsuttu PR-algoritmi.