什么是Dijkstra算法

什么是Dijkstra算法，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

迪杰斯特拉(Dijkstra)算法是求解“圖”中單源最短路徑的算法之一，所謂單源最短路徑是指給定一個(gè)“初始節(jié)點(diǎn)”，求解其到其它各頂點(diǎn)的最短路徑。

為了方便描述，假設(shè)圖中所有邊的權(quán)重都不為負(fù)：

該圖已經(jīng)較簡潔，并且方便對(duì)該算法進(jìn)行描述：

假設(shè)1號(hào)節(jié)點(diǎn)為指定的開始節(jié)點(diǎn)，現(xiàn)欲求1號(hào)節(jié)點(diǎn)到2、3、4號(hào)各節(jié)點(diǎn)的最短路徑。其中1號(hào)到2號(hào)節(jié)點(diǎn)的求解過程如下：

（1）由于1號(hào)節(jié)點(diǎn)與2、3、4號(hào)節(jié)點(diǎn)直接相連的路徑分別為w6、w5、w1（我們將這幾個(gè)路徑放到一個(gè)臨時(shí)的集合中，并試圖從中選擇一個(gè)到其它節(jié)點(diǎn)中路徑最短的那個(gè)）。

（2）如果臨時(shí)集合中w6為其中的最短路徑，則w6為最終結(jié)果，關(guān)鍵問題是w1 -> w4，w1 -> w3 -> w2，w5 -> w2，w5 -> w3 -> w4也是其余的4條路徑。所以我們假設(shè)（1）中w1為與1號(hào)節(jié)點(diǎn)直連路徑中最短的那條（因此w1為1號(hào)節(jié)點(diǎn)和4號(hào)節(jié)點(diǎn)的最短路徑，我們將4號(hào)節(jié)點(diǎn)放入到最終的最短路徑集合中）。

（3）對(duì)于4號(hào)節(jié)點(diǎn)，除了直連的1號(hào)節(jié)點(diǎn)外，還有其余的2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)。如果w1 -> w4的路徑和小于w6，那么臨時(shí)集合中1號(hào)與2號(hào)節(jié)點(diǎn)的最短路徑需更新為w1+w4（假設(shè)更新）。同理w1 -> w3的路徑和小于w5，則臨時(shí)集合中1號(hào)與3號(hào)節(jié)點(diǎn)的最短路徑需更新為w1+w3（假設(shè)更新，注意我們的目標(biāo)是求1號(hào)到2號(hào)節(jié)點(diǎn)的最短路徑，但是該算法會(huì)附帶著求解到其它節(jié)點(diǎn)的最短路徑）。

（4）目前為止在臨時(shí)集合中保存著1號(hào)節(jié)點(diǎn)分別到2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)的最短路徑，現(xiàn)按照（2）的步驟從其中選擇一條最短路徑來，如果選擇2號(hào)節(jié)點(diǎn)則為最終結(jié)果，如果選擇3號(hào)節(jié)點(diǎn)則需要按照（3）的步驟進(jìn)一步判斷如果w1 -> w3 -> w2的路徑和小于w1 -> w4則最終的最短路徑更新為w1+w3+w2。

注意：以上就是該算法的全過程，而且前提條件是權(quán)重不為負(fù)。那么假設(shè)權(quán)重可能為負(fù)則該算法的第（1）步就不能實(shí)現(xiàn)，因?yàn)橐婚_始就不能選擇一個(gè)到其它節(jié)點(diǎn)中路徑最短的那個(gè)節(jié)點(diǎn)（可以假設(shè)w2為負(fù)，這樣w6不一定是最短路徑），這是前提條件。當(dāng)然該算法在真正實(shí)現(xiàn)的時(shí)候還需要考慮一下權(quán)重相等的情況。

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。