單源最短路徑

發(fā)布時(shí)間：2020-09-13 07:57:02 來(lái)源：網(wǎng)絡(luò) 閱讀：537 作者：zmh009_NAME 欄目：開(kāi)發(fā)技術(shù)

以下為找到一條單源最短路徑的思想與思路描述

自己最近看了一下關(guān)于單源最短路徑的算法，其基礎(chǔ)是DijKstra算法：從某個(gè)起點(diǎn)開(kāi)始，選擇直接連接的最短路徑點(diǎn)，更新最短路徑長(zhǎng)并逐漸擴(kuò)到終點(diǎn)。

如圖所示的路徑：（手工畫(huà)圖，若丑勿怪單源最短路徑）

單源最短路徑起點(diǎn)為1，尋找到終點(diǎn)3，則操作如下：

一、1找到直接相連的點(diǎn)及其路徑長(zhǎng)：2(9)、4(6)、5(11)，更新點(diǎn)的最短路徑數(shù)據(jù)，此時(shí)4(6)路徑最短，則以4(6)為起點(diǎn)尋找；

二、4找到5(6+6=12)，此時(shí)12 > 11不更新，則4(6)點(diǎn)尋找完畢，未結(jié)束；

三、此時(shí)已找的最短路徑點(diǎn)為2(9)，則點(diǎn)2可找到點(diǎn)3(9+12=21)并更新，此時(shí)2(9)點(diǎn)尋找完畢，21非最短距離，未結(jié)束；

四、此時(shí)可繼續(xù)尋找的點(diǎn)為5(11)，直接連接的點(diǎn)為3(11+5=16)，此時(shí)16 < 21則更新點(diǎn)3(21)為3(16)，此時(shí)點(diǎn)5尋找完畢；

五、此時(shí)在可尋找的點(diǎn)里3(16)為最短路徑且3為終點(diǎn)（此處只有點(diǎn)3），尋找完畢；

總結(jié)：

對(duì)每個(gè)點(diǎn)存儲(chǔ)到該點(diǎn)對(duì)應(yīng)的最短路徑，如果有最短的路徑則更新（初始每個(gè)路徑長(zhǎng)為無(wú)窮大）；

從起點(diǎn)開(kāi)始尋找可直接連接的點(diǎn)并更新路徑；
如果無(wú)直接連接點(diǎn)或無(wú)更新點(diǎn)，則改點(diǎn)尋找結(jié)束，并找下一個(gè)有最短路徑點(diǎn)開(kāi)始；
如果有最短路徑的點(diǎn)則再次尋找并更新路徑；
如果找到終點(diǎn)且該終點(diǎn)路徑為可繼續(xù)尋找路徑的點(diǎn)里的最短路徑，則該路徑為單源最短路徑；

向AI問(wèn)一下細(xì)節(jié)

猜你喜歡