[發(fā)明專利]改進(jìn)迪杰斯特拉算法的兩點(diǎn)間最短路徑搜索方法

有效

• 申請?zhí)枺?/td>: 201611051320.5
• 申請日: 2016-11-24
• 公開（公告）號: CN107276896B
• 公開（公告）日: 2020-03-27
• 發(fā)明（設(shè)計(jì)）人: 和敬涵;王紫琪;張大海;李文立;丁凡凡;張秋芳;張義志;任欣玉
• 申請（專利權(quán)）人: 北京交通大學(xué)
• 主分類號: H04L12/721
• 分類號: H04L12/721
• 代理公司: 北京鴻元知識產(chǎn)權(quán)代理有限公司 11327
• 代理人: 陳英俊;楊樺

本發(fā)明提供了一種改進(jìn)迪杰斯特拉算法的兩點(diǎn)間最短路徑搜索方法，包括有以下步驟：1)引入了圖論思想中的鄰接矩陣，利用鄰接矩陣對搜索過程進(jìn)行輔助，即每次確定了某一頂點(diǎn)到起始頂點(diǎn)的最短距離后，都查找鄰接矩陣中，該頂點(diǎn)所對應(yīng)的行中元素為1的列；2)只對步驟1)元素為1的列所對應(yīng)的頂點(diǎn)距離值進(jìn)行計(jì)算分析，有效降低搜索過程的計(jì)算量。本發(fā)明基于鄰接矩陣進(jìn)行路徑分析避免了不相連節(jié)點(diǎn)的無用計(jì)算過程，有效減小計(jì)算量，同時(shí)保證了搜索路徑最短。

技術(shù)領(lǐng)域

本發(fā)明涉及電力系統(tǒng)網(wǎng)絡(luò)、道路交通、通信網(wǎng)絡(luò)等領(lǐng)域，具體地說，涉及一種改進(jìn)迪杰斯特拉算法的兩點(diǎn)間最短路徑搜索方法。

背景技術(shù)

求取任意兩點(diǎn)間的最短路徑，是所有求解路徑問題的基礎(chǔ)，問題的目標(biāo)是找到圖中任意兩個(gè)頂點(diǎn)之間的最短路徑。它在電力系統(tǒng)網(wǎng)絡(luò)、道路交通、通信網(wǎng)絡(luò)尋優(yōu)等領(lǐng)域具有廣泛的用途。

對于兩點(diǎn)間的最短路徑計(jì)算問題，國際上采用較多的方法主要是Dijkstra算法(迪杰斯特拉算法)，此算法可以找出網(wǎng)絡(luò)中從一點(diǎn)到其余各點(diǎn)間的最短路徑。Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。

1、Dijkstra算法思想：

按路徑長度遞增次序產(chǎn)生算法：

把頂點(diǎn)集合V分成兩組：

(1)S：已求出的頂點(diǎn)的集合(初始時(shí)只含有源點(diǎn)V0)

(2)V-S＝T：尚未確定的頂點(diǎn)集合

將T中頂點(diǎn)按遞增的次序加入到S中，保證：

(1)從源點(diǎn)V0到S中其他各頂點(diǎn)的長度都不大于從V0到T中任何頂點(diǎn)的最短路徑長度

(2)每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離值

S中頂點(diǎn)：從V0到此頂點(diǎn)的長度

T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長度

依據(jù)：可以證明V0到T中頂點(diǎn)Vk的，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和

2、算法步驟如下(以搜索V0到V1最短路徑為例)：

建立拓?fù)浣Y(jié)構(gòu)圖G＝{V，E}

(1)初始時(shí)令S＝{V0}，T＝V-S＝{其余頂點(diǎn)}，T中頂點(diǎn)對應(yīng)的距離值

若存在<V0，Vi>，d(V0，Vi)為<V0，Vi>弧上的權(quán)值

若不存在<V0，Vi>，d(V0，Vi)為∞

(2)從T中選取一個(gè)與S中頂點(diǎn)有關(guān)聯(lián)邊且權(quán)值最小的頂點(diǎn)W，加入到S中

(3)對其余T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從V0到Vi的距離值縮短，則修改此距離值

重復(fù)上述步驟2、3，直到S中包含所有頂點(diǎn)，即W＝Vi為止。此時(shí)V0到V1距離即兩個(gè)節(jié)點(diǎn)間最短距離。搜索過程，距離值變化時(shí)歷經(jīng)的節(jié)點(diǎn)及路徑，即為兩點(diǎn)間最短路徑。

現(xiàn)有Dijkstra算法每次將頂點(diǎn)放入S中時(shí)候，搜索都需要對T中剩余的全部節(jié)點(diǎn)進(jìn)行分析處理，計(jì)算量大。

發(fā)明內(nèi)容

本發(fā)明旨在克服現(xiàn)有迪杰斯特拉算法的不足，提供一種改進(jìn)迪杰斯特拉算法的兩點(diǎn)間最短路徑搜索方法，基于鄰接矩陣進(jìn)行路徑分析避免了不相連節(jié)點(diǎn)的無用計(jì)算過程，有效減小計(jì)算量同時(shí)保證了搜索路徑最短，既可以準(zhǔn)確確定最短路徑及距離，也能提高運(yùn)算速度。