大众科技
大衆科技
대음과기
DAZHONG KEJI
2015年
2期
1-3,5
,共4页
Dijkstra最短路径算法%最短时间路径%交通运输%网络优化
Dijkstra最短路徑算法%最短時間路徑%交通運輸%網絡優化
Dijkstra최단로경산법%최단시간로경%교통운수%망락우화
Dijkstra shortest path algorithm%the shortest time path%communication and transportation%network optimization
Dijkstra最短路径算法广泛应用于交通运输和网络优化等领域，但是在实际应用的过程中仍存在一些不足。文章针对道路拥挤、交叉路口等待和单行道限行等方面提出了一种改进的基于时间最短的最短路径算法。传统的最短路径算法中图的顶点是抽象的，不含权重的，改进的算法中图的顶点是有权值的，用来表示道路交叉口的等待时间。通过编程实现该算法，实验结果表明，道路拥挤、交叉口等待和单行道限行对交通路径选择有很大影响。因此，改进的算法求得的最短时间路径更加符合实际，具有一定的应用价值。
Dijkstra最短路徑算法廣汎應用于交通運輸和網絡優化等領域，但是在實際應用的過程中仍存在一些不足。文章針對道路擁擠、交扠路口等待和單行道限行等方麵提齣瞭一種改進的基于時間最短的最短路徑算法。傳統的最短路徑算法中圖的頂點是抽象的，不含權重的，改進的算法中圖的頂點是有權值的，用來錶示道路交扠口的等待時間。通過編程實現該算法，實驗結果錶明，道路擁擠、交扠口等待和單行道限行對交通路徑選擇有很大影響。因此，改進的算法求得的最短時間路徑更加符閤實際，具有一定的應用價值。
Dijkstra최단로경산법엄범응용우교통운수화망락우화등영역，단시재실제응용적과정중잉존재일사불족。문장침대도로옹제、교차로구등대화단행도한행등방면제출료일충개진적기우시간최단적최단로경산법。전통적최단로경산법중도적정점시추상적，불함권중적，개진적산법중도적정점시유권치적，용래표시도로교차구적등대시간。통과편정실현해산법，실험결과표명，도로옹제、교차구등대화단행도한행대교통로경선택유흔대영향。인차，개진적산법구득적최단시간로경경가부합실제，구유일정적응용개치。
Dijkstra shortest path algorithm(DSPA) is widely used in fields of communication and transportation and network optimization, etc. But there are still some shortcomings in the process of practical application. We propose an improved SPA based on the minimum duration which is directing at the aspects such as congested roads, the intersection waiting and one-way street restrictions. The vertex of diagram in tradition SPA is abstract and does not contain the weight, while does and is used to represent the intersections waiting time in improved algorithm.We program to implement it and the results show that the above three aspects mentioned has a great influence on choice of the transportation route. Therefore, the shortest time path wh3ich is gained by the improved algorithm is more in line with the actual and the improved algorithm has a certain application value.
