Home // AICT 2013, The Ninth Advanced International Conference on Telecommunications // View article

Efficiency Evaluation of Shortest Path Algorithms

Authors:
Mariusz Głąbowski
Bartosz Musznicki
Przemysław Nowak
Piotr Zwierzykowski

Keywords: shortest path, algorithms, efficiency, evaluation

Abstract:
While the ever growing computational capabilities of devices that are used for man-machine interaction are taken for granted, the need to find their most optimum use is as important as ever. This issue is particularly relevant when considering solutions where the determination of the shortest path between given points (nodes) is one of the basic operations. In more complex executions of the shortest paths, sets of paths with the shortest distance between a single initial (source) point and all other destination points, as well as between all pairs of points, are to be found. For each of these approaches, individual algorithms with specific features have been worked out over the past decades. With that in mind, the present article seeks to explore this problem and is structured in such a way as to describe some of the selected algorithms solving the shortest path problem, and to analyse the efficiency of these algorithms during their operation in directed graphs of different type. The~study shows that the efficiency varies among algorithms under investigation and allows to suggest which one ought to be used to solve a specific variant of the shortest path problem.

Pages: 154 to 160

Copyright: Copyright (c) IARIA, 2013

Publication date: June 23, 2013

Published in: conference

ISSN: 2308-4030

ISBN: 978-1-61208-279-0

Location: Rome, Italy

Dates: from June 23, 2013 to June 28, 2013