有向非負權圖中經過必經節點集最短路徑算法

楊志勇 ，葉馮彬 ，馮艷輝 ，劉秀秀 ，朱 巖

（1.中國科學院大學 北京 100049；2.中國科學院國家空間科學中心 北京 100190；3.成都理工大學 成都610059）

有向非負權圖中經過必經節點集最短路徑算法

楊志勇1，2，葉馮彬3，馮艷輝1，2，劉秀秀1，2，朱 巖2

（1.中國科學院大學 北京 100049；2.中國科學院國家空間科學中心 北京 100190；3.成都理工大學 成都610059）

傳統的Dijkstra算法只是針對起點和終點求解最短路徑，而不能解決從起點出發，經過必經節點集，到達終點的無重復節點且無回路的最短路徑問題。為此，在有向非負權圖中，提出了Dijkstra算法和回溯法相結合的方法。對Dijkstra算法改進，并求解關鍵節點（起點，終點和必經節點）間的最短路徑，進而從關鍵節點所構成的矩陣中采用回溯法得到目標路徑。通過實際的算法實現，測試大量的有向非負權圖數據，證實了算法的有效性和正確性。

Dijkstra算法；回溯法；深度優先搜索；最短路徑；必經節點集；有向非負權圖

最短路徑（SP）算法，可以用來解決道路設計和網絡路由等諸多動態規劃和優化的問題。EW.A Dijkstra于1959年提出著名的Dijkstra算法[1]，用于計算一個節點到其他所有節點的最短路徑，其主要思想是以起點為中心向外一層一層輻射迭代，直到輻射到終點為止。

以Dijkstra為原型，研究人員提出了對最短路徑問題[2-4]的諸多優化方案。針對Dijkstra算法的復雜性，提出一種新的時空復雜度更低的改進算法[5-7]；采用配對堆結構實現路徑計算過程中的優先級隊列的一系列操作，提高算法的效率和性能[8]；對Dijkstra標號法改進，實現起點和終點之間的最短路徑[9]；……