AbstractsComputer Science

An Evaluation of Shortest Path Algorithms on Real Metropolitan Area Networks

by David Johansson




Institution: Linköping University
Department:
Year: 2008
Keywords: Shortest path; Least hops path; Dijkstra; Computer networks; Bidirectional algorithm; Heap implementation; Performance; Natural Sciences; Computer and Information Science; Computer Science; Naturvetenskap; Data- och informationsvetenskap; Datavetenskap (datalogi); TECHNOLOGY; Information technology; Computer science; TEKNIKVETENSKAP; Informationsteknik; Datavetenskap; Computer and information science at the Institute of Technology; Datavetenskap vid LiTH; teknik; teknik
Record ID: 1362673
Full text PDF: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-17491


Abstract

This thesis examines some of the best known algorithms for solving the shortest point-to-point path problem, and evaluates their performance on real metropolitan area networks. The focus has mainly been on Dijkstra‟s algorithm and different variations of it, and the algorithms have been implemented in C# for the practical tests. The size of the networks used in this study varied between 358 and 2464 nodes, and both running time and representative operation counts were measured. The results show that many different factors besides the network size affect the running time of an algorithm, such as arc-to-node ratio, path length and network structure. The queue implementation of Dijkstra‟s algorithm showed the worst performance and suffered heavily when the problem size increased. Two techniques for increasing the performance were examined: optimizing the management of labelled nodes and reducing the search space. A bidirectional Dijkstra‟s algorithm using a binary heap to store temporarily labelled nodes combines both of these techniques, and it was the algorithm that performed best of all the tested algorithms in the practical tests. This project was initiated by Netadmin Systems i Sverige AB who needed a new path finding module for their network management system NETadmin. While this study is primarily of interest for researchers dealing with path finding problems in computer networks, it may also be useful in evaluations of path finding algorithms for road networks since the two networks share some common characteristics.