关键词: 最短路径, 关键边, Dijkstra算法, 最优路径

Abstract: Aiming at the problem of ineffective temporary shortest distribution path caused by road congestion such as holidays, this paper proposes an optimal route selection model for distribution network, and designs an algorithm to solve the key edges and optimal path of express distribution network. Firstly, the key edges of the whole network are calculated and the characteristics of distribution network are mastered. Secondly, considering the customer’s time requirement, the optimal path under incomplete information(interruption can not be predicted in advance, only when it reaches the starting point of interruption edge)is studied. According to the new characteristics of each side of the shortest path, a set of reserve paths corresponding to each side after interruption are calculated, and then the paths with transportation time less than or equal to the waiting time of customers are selected as the effective paths. Considering road congestion, the optimal paths are selected from the effective paths. Finally, according to the actual situation of distribution network, the optimal paths are selected. An example is given to analyze the optimal path.

Key words: shortest path, critical edge, dijkstra algorithm, optimal path