,
ICPM'2011

Improvement of shortest path algorithms through graph partitioning
Author: Ivan Šimeček, Filip Šimek
Keywords

Dijkstra's shortest path algorithm; graph theory; road network; graph partition


Abstract

Route planning problem occurs often in many practical areas of life including problem of finding of optimal paths in road networks. This paper presents an algorithm based upon traditional graph algorithms, like the Dijkstra's shortest path algorithm but it takes advantage of the specific properties of a road network graph. Presented modification of algorithm partitions a given graph into smaller components, it results in efficient execution even for large-scale graphs. Searching in smaller components still guarantee optimality of solution.

 

Download:
final version (in .PDF format)

BibTex entry:
@inproceedings{JA_ICPM11b,
author = {{\v S}ime{\v c}ek, I. and {\v S}imek, F.},
title = {{Improvement of shortest path algorithms through graph partitioning}},
booktitle = {{Proceedings of International Conference PRESENTATION of MATHEMATICS '11}},
publisher = {Technical University},
address = {Liberec},
year = {2011},
pages = {131--137},
ISBN = {978-80-7372-773-4},
language = {English}
}

BACK