Finding the shortest paths by node combination
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
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.
Shortest path, Node combination, Node combination algorithm, Dijkstra's algorithm, Weight matrix
IdentifiersURN: urn:nbn:se:su:diva-67897DOI: 10.1016/j.amc.2011.01.019ISI: 000287690400042OAI: oai:DiVA.org:su-67897DiVA: diva2:472142
authorCount :22012-01-032012-01-022012-09-19Bibliographically approved