Description: Finding the shortest path in a graph with a finite number of nodes is a well-known optimization problem, can be efficiently solved by Dijsktra's algorithm, for instance. But what happens, when we have to find the shortest path in a terrain, where there are shapes with different speeds allowed? This is called the weighted regions problem in the literature. The student has to implement a software to edit and/or visualize a terrain with polygons of different speed rates, called regions, an algorithm, to find shortest paths between points between, and to visualize the results. The best or approximate solutions are to be found, the literature can be used to refer to the algorithm, and any platform is allowed for implementation.
Supervisor: András Éles