Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:su:diva-67897DOI: 10.1016/j.amc.2011.01.019ISI: 000287690400042OAI: diva2:472142

authorCount :2

Available from: 2012-01-03 Created: 2012-01-02 Last updated: 2012-09-19Bibliographically 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
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

Altmetric score

Total: 160 hits
ReferencesLink to record
Permanent link

Direct link