Change search
ReferencesLink to record
Permanent link

Direct link
Compressing sparse graphs to speed up Dijkstra’s shortest path algorithm
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

One of the problems that arises from the continuously growing amount of data is that it slows down and limits the uses of large graphs in real world situations. Because of this, studies are being done to investigate the possibility of compressing data in large graphs. This report presents an investigation on the usefulness of compressing sparse graphs and then applying Dijkstra’s shortest path algorithm. A minimal spanning tree algorithm was used to compress a graph and compared with a self-implemented compression algorithm. The minimal distances and how long time it takes for Dijkstra's algorithm to find the shortest path between nodes are investigated.

The results show that it is not worth compressing the type of sparse graphs used in this study. It is hard to compress the graph without losing too much of the edges that preserve the shortest paths. The time gained when running Dijkstra's algorithm on the compressed graphs is not enough to compensate for the lack of getting a good shortest path solution.

Place, publisher, year, edition, pages
National Category
Computer Science
URN: urn:nbn:se:kth:diva-166730OAI: diva2:812016
Available from: 2015-05-28 Created: 2015-05-14 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

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

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

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

Direct link