Change search
ReferencesLink to record
Permanent link

Direct link
K Shortest Path Implementation
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The problem of computing K shortest loopless paths, or ranking of the K shortest loopless paths between a pair of given vertices in a network is a well-studied generalization of shortest path problem. The K shortest paths problem determines not only one shortest path but the K best shortest paths from s to t in an increasing order of weight of the paths.

Yen’s algorithm is known to be the efficient and widely used algorithm for determining K shortest loopless paths. Here, we introduce a new algorithm by modifying the Yen’s algorithm in the following way: instead of removing the vertices and the edges from the graph, we store them in two different sets. Then we modified the Dijkstra’s algorithm by taking these two sets into consideration. Thus the algorithm applies glass box methodology by using the modified Dijkstra’s algorithm for our dedicated purpose. Thus the efficiency is improved. The computational results conducted over different datasets, shows the proposed algorithm has better performance results.

Place, publisher, year, edition, pages
2013. , 43 p.
Keyword [en]
K Shortest Path, Yen's, Shortest Path Algorithm, Deviation paths, K shortest loopless paths
National Category
Computer Systems
URN: urn:nbn:se:liu:diva-95451ISRN: LIU-IDA/LITH-EX-A--13/041--SEOAI: diva2:635314
Subject / course
Master's programme in Computer Science
2013-06-27, Muhammad al-Khwarizmi, Linkoping University, Linkoping, 13:00 (English)
Available from: 2013-07-04 Created: 2013-07-03 Last updated: 2015-02-18Bibliographically approved

Open Access in DiVA

K_Shortest_Path_Imp(1113 kB)959 downloads
File information
File name FULLTEXT01.pdfFile size 1113 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nagubadi, RadhaKrishna
By organisation
Database and information techniquesThe Institute of Technology
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 959 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: 365 hits
ReferencesLink to record
Permanent link

Direct link