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

在審

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

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

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

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

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

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

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

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

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

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

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

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為當前到達目的結(jié)點的可走路徑數(shù)目，NodeList_W|_W＝Wc表示當前到達水流W_c經(jīng)過目的結(jié)點的鏈表，reachTime_W|_W＝Wc表示當前到達水流W_c的到達時間，v_i為第i條可走路徑上的權(quán)值。