An Optimization Dijkstra Algorithm Based on Two-Function Limitation Strategy
Yihu Huang, Genmin Zhang, Jinli Wang · 2009
There are two problems in searching the shortest path by Dijkstra algorithm. One is that the practical application of the result is not satisfactory because of the fixed weights; the other is that the time complexity is very high because of searching all nodes. So two-function limitation strategy is presented in this paper. One is that the weights are dynamic evaluated by adaptive function in order to limit the number of bad paths and improve the practicality of Dijkstra algorithm. The other is that the number of reaching nodes is limited by heuristic function according to dynamic weights in order to reduce the time complexity. According to the simulation results, we get the conclusion that two-function limitation strategy can reduce the number of bad paths by 89.2% and improve search efficiency by 58.3%.