Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computing k shortest paths from a source node to each other node
Show others and affiliations
2015 (English)In: Soft Computing - A Fusion of Foundations, Methodologies and Applications, ISSN 1432-7643, E-ISSN 1433-7479, Vol. 19, no 8, p. 2391-2402Article in journal (Refereed) Published
Abstract [en]

The single-pair K shortest path (KSP) problem can be described as finding k least cost paths through a graph between two given nodes in a non-decreasing order, while single-source KSP algorithms aim to find KSPs from a given node to each other node. However, little effort has been devoted to the single-source KSP approaches. This paper proposes a novel single-source KSP algorithm in a given directed weighted graph where loops are allowed. The proposed method is designed to compute a set of shortest paths with exactly k distinctive lengths in a non-decreasing order. Meanwhile, it can also find all shortest paths with the length less than a given threshold. Inspired by water flowing principle, we imagine that there are waters flowing from a source node to each other node along edges at a constant speed. When the water reaches a node, the node will generate new waters flowing along its outgoing edges. By stepping back the traces of the water, the ordered shortest paths can be obtained. We also address the correctness and effectiveness of the method. Simulations are carried out using synthetic data and practical graph data, which demonstrate the considerable performance of the proposed approach especially for single-source KSP problems.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2015. Vol. 19, no 8, p. 2391-2402
Keyword [en]
K shortest path problem, Single-pair KSP, Single-source KSP
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-174942DOI: 10.1007/s00500-014-1434-2ISI: 000361484700022Scopus ID: 2-s2.0-84937419139OAI: oai:DiVA.org:kth-174942DiVA, id: diva2:862467
Note

QC 20151022

Available from: 2015-10-22 Created: 2015-10-09 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Takacs, Alexander
By organisation
School of Computer Science and Communication (CSC)
In the same journal
Soft Computing - A Fusion of Foundations, Methodologies and Applications
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 101 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf