计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
5期
223-228
,共6页
最短路径%Dijkstra标号法%城市交通%最优路线选择
最短路徑%Dijkstra標號法%城市交通%最優路線選擇
최단로경%Dijkstra표호법%성시교통%최우로선선택
求最短路径是一个应用很广泛的问题.求最短路径的算法有很多,公认较好的算法是Dijkstra标号法.但实验结果表明,Dijkstra标号法有需要改进的地方:①其退出机制对不联通的有向图是无效的,会陷入死循环；②没有涉及最短路径上顶点的邻接点(特指前面的相邻点)问题；③没有涉及多个顶点同时获得p标号的问题.针对上述问题,对标号法进行了改进.算法实验表明,改进的标号法能够有效解决上述问题.在上述工作的基础上,开发了“北京市道路最优路线选择系统”,以提供起点和终点之间的最优路线,帮助用户选择出行路线,使市民能够避过交通最拥堵的路段,节约出行时间.
求最短路徑是一箇應用很廣汎的問題.求最短路徑的算法有很多,公認較好的算法是Dijkstra標號法.但實驗結果錶明,Dijkstra標號法有需要改進的地方:①其退齣機製對不聯通的有嚮圖是無效的,會陷入死循環；②沒有涉及最短路徑上頂點的鄰接點(特指前麵的相鄰點)問題；③沒有涉及多箇頂點同時穫得p標號的問題.針對上述問題,對標號法進行瞭改進.算法實驗錶明,改進的標號法能夠有效解決上述問題.在上述工作的基礎上,開髮瞭“北京市道路最優路線選擇繫統”,以提供起點和終點之間的最優路線,幫助用戶選擇齣行路線,使市民能夠避過交通最擁堵的路段,節約齣行時間.
구최단로경시일개응용흔엄범적문제.구최단로경적산법유흔다,공인교호적산법시Dijkstra표호법.단실험결과표명,Dijkstra표호법유수요개진적지방:①기퇴출궤제대불련통적유향도시무효적,회함입사순배；②몰유섭급최단로경상정점적린접점(특지전면적상린점)문제；③몰유섭급다개정점동시획득p표호적문제.침대상술문제,대표호법진행료개진.산법실험표명,개진적표호법능구유효해결상술문제.재상술공작적기출상,개발료“북경시도로최우로선선택계통”,이제공기점화종점지간적최우로선,방조용호선택출행로선,사시민능구피과교통최옹도적로단,절약출행시간.
