liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
An Evaluation of Shortest Path Algorithms on Real Metropolitan Area Networks
Linköping University, Department of Computer and Information Science.
2008 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
2008. , 66 p.
Keyword [en]
Shortest path, Least hops path, Dijkstra, Computer networks, Bidirectional algorithm, Heap implementation, Performance
National Category
Computer Science
URN: urn:nbn:se:liu:diva-17491ISRN: LIU-IDA/LITH-EX-A--08/059--SEOAI: diva2:209718
2008-12-18, Alan Turing, IDA, Linköpings universitet, Linköping, 10:00 (Swedish)
Available from: 2009-03-30 Created: 2009-03-26 Last updated: 2009-03-30Bibliographically approved

Open Access in DiVA

fulltext(1190 kB)883 downloads
File information
File name FULLTEXT01.pdfFile size 1190 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Computer and Information Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 883 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 654 hits
ReferencesLink to record
Permanent link

Direct link