溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
以下為找到一條單源最短路徑的思想與思路描述
自己最近看了一下關于單源最短路徑的算法，其基礎是DijKstra算法：從某個起點開始，選擇直接連接的最短路徑點，更新最短路徑長并逐漸擴到終點。
如圖所示的路徑：（手工畫圖，若丑勿怪
）
起點為1，尋找到終點3，則操作如下：
一、1找到直接相連的點及其路徑長：2(9)、4(6)、5(11)，更新點的最短路徑數據，此時4(6)路徑最短，則以4(6)為起點尋找；
二、4找到5(6+6=12)，此時12 > 11不更新，則4(6)點尋找完畢，未結束；
三、此時已找的最短路徑點為2(9)，則點2可找到點3(9+12=21)并更新，此時2(9)點尋找完畢，21非最短距離，未結束；
四、此時可繼續尋找的點為5(11)，直接連接的點為3(11+5=16)，此時16 < 21則更新點3(21)為3(16)，此時點5尋找完畢；
五、此時在可尋找的點里3(16)為最短路徑且3為終點（此處只有點3），尋找完畢；
總結：
對每個點存儲到該點對應的最短路徑，如果有最短的路徑則更新（初始每個路徑長為無窮大）；
從起點開始尋找可直接連接的點并更新路徑；
如果無直接連接點或無更新點，則改點尋找結束，并找下一個有最短路徑點開始；
如果有最短路徑的點則再次尋找并更新路徑；
如果找到終點且該終點路徑為可繼續尋找路徑的點里的最短路徑，則該路徑為單源最短路徑；
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
