[發(fā)明專利]一種多條最短路徑的快速尋找方法

在審

• 申請?zhí)枺?/td>: 201711045402.3
• 申請日: 2017-10-31
• 公開（公告）號(hào): CN107860393A
• 公開（公告）日: 2018-03-30
• 發(fā)明（設(shè)計(jì)）人: 劉靖宇
• 申請（專利權(quán)）人: 劉靖宇
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 成都弘毅天承知識(shí)產(chǎn)權(quán)代理有限公司51230
• 代理人: 徐金瓊,劉東

1.一種多條最短路徑的快速尋找方法，其特征在于，包括以下步驟：

(1)導(dǎo)入地圖，用戶確定源結(jié)點(diǎn)和各目的結(jié)點(diǎn)，以及所需尋找的最短路徑數(shù)目K，即源結(jié)點(diǎn)到每一個(gè)目的結(jié)點(diǎn)都要求出最短的K條路徑；

(2)定義水流數(shù)據(jù)結(jié)構(gòu)W(NodeList，reachTime)，WList和P，其中W表示一股水流，NodeList是一個(gè)鏈表，保存水流已經(jīng)經(jīng)過的目的結(jié)點(diǎn)以及即將流入的目的結(jié)點(diǎn)，reachTime表示水流到達(dá)NodeList中各目的結(jié)點(diǎn)的時(shí)間，WList中存儲(chǔ)的是當(dāng)前網(wǎng)路中流動(dòng)的水流，并按到達(dá)時(shí)間升序排列，P中存儲(chǔ)了源結(jié)點(diǎn)到每個(gè)目的結(jié)點(diǎn)的最短的K條路徑；

(3)初始化數(shù)據(jù)結(jié)構(gòu)，從源結(jié)點(diǎn)沿可走路徑引出恒速水流W₁,…,W_J，J為源結(jié)點(diǎn)可走路徑的數(shù)目；將W₁,…,W_J按到達(dá)時(shí)間升序排列插入WList中；

(4)從WList中取出第一條水流信息W_c，并將WList中的W_c刪除，取出W_c中目的結(jié)點(diǎn)N_t，在P中查看N_t是否已經(jīng)找到了K條路徑，若是，終止該目的結(jié)點(diǎn)N_t水流分流，轉(zhuǎn)到步驟(6)，否則，轉(zhuǎn)到步驟(5)；

(5)將W_c中NodeList分量保存到P中，接著分流目的結(jié)點(diǎn)N_t之前，判斷目的結(jié)點(diǎn)N_t分流到達(dá)的目的結(jié)點(diǎn)是否在P的NodeList分量中，若沒有,將目的結(jié)點(diǎn)N_t分流后到達(dá)的目的結(jié)點(diǎn)按水流到達(dá)時(shí)間的升序插入到WList中,否則放棄該可走路徑；

(6)判斷WList是否為空，若是，結(jié)束程序返回P，否則轉(zhuǎn)到步驟(4)。

2.根據(jù)權(quán)利要求1所述的一種多條最短路徑的快速尋找方法，其特征在于，所述步驟(3)中，源結(jié)點(diǎn)沿可走路徑引出的恒速水流的公式如下：

NodeList_W|_W＝Wj＝(n₀,n_j),reachTime_W|_W＝Wj＝v_j

其中，v_j為第j條可走路徑上的權(quán)值，j＝1,…,J，n₀為源結(jié)點(diǎn)，n_j為第j條可走路徑上的目的結(jié)點(diǎn)。

3.根據(jù)權(quán)利要求2所述的一種多條最短路徑的快速尋找方法，其特征在于，步驟(5)的具體步驟如下：

插入到WList中的分量的更新公式如下：

NodeList_W|_W＝Wi＝NodeList_W|_W＝Wc+N_t；

reachTime_W|_W＝Wi＝reachTime_W|_W＝Wc+v_i(i＝1,…,M)；

其中，i＝1,…,M，M為當(dāng)前到達(dá)目的結(jié)點(diǎn)的可走路徑數(shù)目，NodeList_W|_W＝Wc表示當(dāng)前到達(dá)水流W_c經(jīng)過目的結(jié)點(diǎn)的鏈表，reachTime_W|_W＝Wc表示當(dāng)前到達(dá)水流W_c的到達(dá)時(shí)間，v_i為第i條可走路徑上的權(quán)值。