Shortest Paths in Euclidean Graphs

Nowadays graph algorithms constitute a broad class of modern algorithms. Graphs can be applied to model relations and processes in informational, physical, biological and social systems. One notable type of graphs is Euclidean graph, which is often used to represent road networks. A frequent task in such networks is determining the shortest route between two sites. There are special Graph Theory algorithms which solve this problem. The goals of this thesis are: to research the means of efficient generation of graphs according to two random Euclidean graph models – Bernoulli Random Graphs and Random Plane Networks; to implement several classical shortest path algorithms and to compare their performance on the generated graphs in different space dimensions. Also, a new heuristical method was suggested and its performance and optimality studied.

Lecture files: