其本質(zhì)是貪心算法，即每一次確定下一步走哪條路都是最為貪心的選擇，也就是按權(quán)值最小作為標(biāo)準(zhǔn)。前提是該路之前沒(méi)被走過(guò)(當(dāng)然走過(guò)的路再走一遍也沒(méi)意義)

這是一個(gè)例子，我在第四步里寫(xiě)了兩種情況，這是在權(quán)值未知的情況下的兩種情況。 這里需要補(bǔ)充的是，這種算法實(shí)際上也是一種遍歷，與遍歷略微不同的是，它將會(huì)對(duì)舊的結(jié)果進(jìn)行覆蓋，那說(shuō)明之前舊的結(jié)果不是兩點(diǎn)之間的最短路徑，目前這個(gè)是已經(jīng)遍歷到的最短的路徑

本質(zhì)就是一次次的循環(huán)，當(dāng)欲訪問(wèn)節(jié)點(diǎn)出現(xiàn)(v5)，就不再往前探索，而是將已經(jīng)存在數(shù)組里但未到達(dá)v5的路徑組繼續(xù)探索，直到路徑組到達(dá)v5，然后將其路徑與之前到達(dá)v5的路徑比較，選擇較小的存起來(lái)，當(dāng)所有的到達(dá)v5的路都探索完了，剩下的那個(gè)就是最短的v0到v5的路徑 這個(gè)算法為什么這么設(shè)計(jì)呢？ 個(gè)人猜測(cè)，這個(gè)和迷宮游戲性質(zhì)類似，只不過(guò)給迷宮的每條路加上權(quán)值而已，但路的權(quán)值只有走過(guò)這條路才知道，走之前是不知道的，試想一下，我想花最小代價(jià)到達(dá)終點(diǎn)，我可以每次都假設(shè)終點(diǎn)就在我將要選擇的路的對(duì)面，而我的目的是代價(jià)最小，那我就走到我目前所知道的最短路徑的點(diǎn)，然后再?gòu)倪@個(gè)點(diǎn)出發(fā)找終點(diǎn)，因?yàn)槿绻K點(diǎn)在對(duì)面那我就走對(duì)了，如果不是終點(diǎn)再另說(shuō)，然后把這條路記在本本上，如果對(duì)面確實(shí)是終點(diǎn)，那么我先記下來(lái)，記下來(lái)我確實(shí)到終點(diǎn)了，但不一定是最小的，因?yàn)槊織l路走之前我是不知道權(quán)值的，所以可能最后到終點(diǎn)的這條路權(quán)值非常大，但只有走過(guò)我才知道，所以我需要回去再把那些沒(méi)走過(guò)的路走一遍走到終點(diǎn)，最后找最小的；但如果沒(méi)到終點(diǎn)，那我得看看我下一步應(yīng)該走哪條路，那么此時(shí)最好的選擇也應(yīng)該是選擇目前存在最短路徑的節(jié)點(diǎn)的路，因?yàn)槲也恢澜K點(diǎn)在哪，我只能說(shuō)保證我之前走的路是最短的，然后一次次嘗試新的路，最后找到終點(diǎn)，再把沒(méi)走過(guò)的路再走一遍

就像這個(gè)較為極端的例子，第一步直接01237到終點(diǎn)，過(guò)程中記錄了5和4的存在，所以到7后我再返回來(lái)看看從3到4這條路能不能通，能通就比較權(quán)值然后取小的放起來(lái)，然后再看看還有5沒(méi)訪問(wèn)，那就去看看1到5這條路怎么樣，通，就比較權(quán)值取小的放起來(lái)，最后發(fā)現(xiàn)路都走完了，那就結(jié)束了，最后省的權(quán)值就是最小的