[發明專利]改進迪杰斯特拉算法的兩點間最短路徑搜索方法

有效

• 申請號: 201611051320.5
• 申請日: 2016-11-24
• 公開（公告）號: CN107276896B
• 公開（公告）日: 2020-03-27
• 發明（設計）人: 和敬涵;王紫琪;張大海;李文立;丁凡凡;張秋芳;張義志;任欣玉
• 申請（專利權）人: 北京交通大學
• 主分類號: H04L12/721
• 分類號: H04L12/721
• 代理公司: 北京鴻元知識產權代理有限公司 11327
• 代理人: 陳英俊;楊樺

1.一種改進迪杰斯特拉算法的兩點間最短路徑搜索方法，其特征在于：

包括有以下步驟：

1)引入了圖論思想中的鄰接矩陣，矩陣中第i行第j列元素表示頂點i和頂點j的連接關系，當頂點i可由拓撲結構圖某一條邊直接到達頂點j時，矩陣第i行第j列的元素為1；否則元素為0，

利用鄰接矩陣對搜索過程進行輔助，即每次確定了某一頂點V到起始頂點的最短距離后，都查找鄰接矩陣中，頂點V所對應的行中元素為1的列；

2)只對步驟1)元素為1的列所對應的且最短路徑未知的頂點的距離值進行計算分析，有效降低計算量；

其中，確定某一頂點V到起始頂點的最短距離的過程包括：

選取某頂點V0作為起始頂點，V1作為終止頂點，以求取V0到V1之間的最短路徑，

步驟1：取網絡中所有節點形成頂點集V，連接這些頂點的線路構成集合E，由頂點集V和線路集E構成拓撲結構圖，記為G(V，E)，并建立鄰接矩陣A：

步驟2：建立集合S和U，初始時，S只包含源點(起始頂點)，即S＝{V0}，V0的距離為0，U包含除V0外的其他頂點，即:U＝{其余頂點}，查找矩陣A中V0所在行，若A中第V0行Vi列數值為1，則U中頂點Vi到V0距離值有權值，權值即為相連線路的長度；若A中第V0行Vi列數值為0，則Vi到V0距離值權值為∞；

步驟3：從U中選取一個距離權值最小的頂點Vk，把Vk加入S中，選定的距離Lk就是V0到Vk的最短路徑長度；

步驟4：查找矩陣A中Vk所在行中元素為1的頂點，如果頂點Vm在集合U中，則以Vk為新考慮的中間點，修改Vm距離；設Vk與Vm連接線路的長度為Lkm，若從源點V0到Vm的距離Lm，經過頂點Vk，Lm＝Lk+Lkm比原來距離短，則修改頂點Vm的距離值為較短的值；

步驟5：重復步驟3和4直到所有頂點都包含在S中，此時V0到V1的距離數值即為兩點間最短路徑長度；所述距離數值產生過程歷經的節點及線路，即為兩點間最短路徑。

2.如權利要求1所述的一種改進迪杰斯特拉算法的兩點間最短路徑搜索方法，其特征在于：

所述圖論思想中的鄰接矩陣，即利用圖論知識構造頂點之間的連接關系，定義圖中頂點集合為V，邊集合為E，建立鄰接矩陣A，A可表示不同頂點之間的相鄰關系；

對于有n個頂點的拓撲結構圖來說，鄰接矩陣A為一個n×n的方陣，行列均為頂點的排列，對應的第i行第j列元素表示頂點i和頂點j的連接關系，當頂點i可由某條邊直接到達頂點j時，鄰接矩陣A中對應位置的元素為1；否則鄰接矩陣對應位置元素為0；即A中元素可表示為：