A Comprehensive Comparison of Label Setting Algorithm and Dynamic Programming Algorithm in Solving Shortest Path Problems

摘要

In this paper, Label Setting Algorithm and Dynamic Programming Algorithm had been critically examined in determining the shortest path from one source to a destination. Shortest path problems are for finding a path with minimum cost from one or more origin (s) to one or more destination(s) through a connected network. A network of ten (10) cities (nodes) was employed as a numerical example to compare the performance of the two algorithms. Both algorithms arrived at the optimal distance of 11 km, which corresponds to the paths 1 → 4 → 5 → 8 → 10,1 → 3 → 5 → 8 → 10 , 1 → 2 → 6 → 9 → 10 and 1 → 4 → 6 → 9 → 10 . Thus, the problem has multiple shortest paths. The computational results evince the outperformance of Dynamic Programming Algorithm, in terms of time efficiency, over the Label Setting Algorithm. Therefore, to save time, it is recommended to apply Dynamic Programming Algorithm to shortest paths and other applicable problems over the Label-Setting Algorithm.