Lyhyimpien reittien etsiminen muuttuvassa graafissa

Abstract

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.

This thesis surveys how to practically implement repetitive shortest path seeking in an undirected graph which changes incrementally between the seekings. The context of the thesis is to create apparently truthful and unplanned city street networks in an environment modeled by the graph. More closely, since streets ease the paths following them, change of the graph is only shortening of its edges. The algorithms surveyed are Dijkstra's algorithm, its extensions and the so-called PR algorithm which is at least theoretically competitive.