Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Finding the shortest paths by node combination
Stockholm University, Faculty of Social Sciences, Department of Sociology.
2011 (English)In: Applied Mathematics and Computation, ISSN 0096-3003, E-ISSN 1873-5649, Vol. 217, no 13, 6401-6408 p.Article in journal (Refereed) Published
Abstract [en]

By repeatedly combining the source node's nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra's algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes' distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra's algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.

Place, publisher, year, edition, pages
2011. Vol. 217, no 13, 6401-6408 p.
Keyword [en]
Shortest path, Node combination, Node combination algorithm, Dijkstra's algorithm, Weight matrix
National Category
Mathematical Analysis
Identifiers
URN: urn:nbn:se:su:diva-67897DOI: 10.1016/j.amc.2011.01.019ISI: 000287690400042OAI: oai:DiVA.org:su-67897DiVA: diva2:472142
Note

authorCount :2

Available from: 2012-01-03 Created: 2012-01-02 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lu, Xin
By organisation
Department of Sociology
In the same journal
Applied Mathematics and Computation
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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