Efficient implementation of algorithms for finding shortest paths

OData support
Supervisor:
Dr. Horváth Gábor
Department of Networked Systems and Services

It is useful to collect knowledge. However it is very important how we use this knowledge. The problem to find shortest paths is exists for a long time in our history. The first known map has been found in 6200 B.C. At this age maps were more like arts then science. Later on during the developing economy and society these maps became more precise and detailed. With these maps the planning of routes (military or merchant) were more easier than before.

In 1950 a dozens of applications were available on computers. Using mathematic objects (like graphs and sets) computers were capable to compute shortest paths. In 1959 Edsger Wybe Dijkstra published an algorithm to find the shotest paths. This algorithm is still in use because of its speed and robust.

The growing traffic and computer networks demand more faster solutions to find shortest paths. The crucial factor in algorithms generally used by GPS navigation and network engineering is the speed.

In this Thesis I will implement efficient algorithms to find shortest paths in CPU and GPU devices. I will study/test/analyze them to show their benefits and drawbacks.

Downloads

Please sign in to download the files of this thesis.