回顧：上次我們說到了狄克斯特拉算法用于每條邊都有關(guān)聯(lián)的圖暴凑，這些數(shù)字稱為權(quán)重峦甩。
新概念：環(huán)，圖中可能有環(huán)搬设，而環(huán)類似下圖這樣穴店。
環(huán)意味著你可從一個(gè)節(jié)點(diǎn)出發(fā)，走一圈后又回到這個(gè)節(jié)點(diǎn)拿穴。假設(shè)在下面這個(gè)帶壞的的圖中泣洞，你要找出從起點(diǎn)到終點(diǎn)的最終路徑。
圖：我們發(fā)現(xiàn)從起點(diǎn)到B的耗時(shí)是2h默色，從B到終點(diǎn)的耗時(shí)是3h球凰，而A和B是一個(gè)環(huán)，這意味著：你可以從A到B腿宰，也可以從B到A呕诉，耗時(shí)都為4h
思路：我們可以避開環(huán)的路徑：從起點(diǎn)到B，再從B到終點(diǎn)吃度，總耗時(shí)5h
?????????? 我們也可以選擇包含環(huán)的路徑：從起點(diǎn)到B甩挫，再從B到A，再從A到B椿每，最后從B到終點(diǎn)伊者。總權(quán)重（耗時(shí)）13h
??????????? 如果你愿意间护，我們甚至可以繞兩次環(huán)亦渗，總權(quán)重為21h
??????????? 但沒繞環(huán)一次，總權(quán)重都增加8.因此汁尺，繞環(huán)的路徑不可能是最短的路徑法精。
這里要注意狄克斯特拉算法只適用于有向無環(huán)圖·
換鋼琴：
術(shù)語介紹的差不多了，我們?cè)賮砜匆粋€(gè)例子：我們的朋友R痴突，想拿一本樂譜換架鋼琴搂蜓。A說：我愿意用海報(bào)換樂譜，如果R再加5元苞也，還可以拿樂譜換R的唱片洛勉。M說：我愿意拿我的吉他和架子鼓換這張海報(bào)和黑膠唱片。B說：我愿意那我的鋼琴換M的吉他或架子鼓如迟。
現(xiàn)在我們知道收毫，我們的朋友只要再花一點(diǎn)點(diǎn)錢，R就能拿樂譜換架鋼琴∫罂保現(xiàn)在R要確定的是此再，如何花最少的錢實(shí)現(xiàn)這個(gè)目標(biāo)，我們來繪制一個(gè)圖玲销，列出大家的交換意愿输拇。
這個(gè)圖中的節(jié)點(diǎn)是大家愿意拿出來交換的東西，邊的權(quán)重是交換時(shí)需要額外加多少錢贤斜。R需要確定采用哪種路徑將樂譜換成鋼琴時(shí)需要支付的額外費(fèi)用最少策吠。因此逛裤，可以使用狄克斯特拉算法，在這個(gè)例子中猴抹，你將完成所有這些步驟带族，因此你也將計(jì)算最終路徑。
動(dòng)手之前蟀给，我們先用一個(gè)表格列出其中每個(gè)節(jié)點(diǎn)的開銷蝙砌，這里的開銷指的是達(dá)到節(jié)點(diǎn)需要額外支付多少錢。
表格：
黑膠唱片：5
海報(bào)：0
吉他：∞
架子鼓：∞
鋼琴：∞
因?yàn)槲覀冞€不知道如何從起點(diǎn)前往這些節(jié)點(diǎn)：我們還沒有更新
在執(zhí)行狄克斯特拉算法的過程中跋理，我們將不斷更新這個(gè)表择克。為計(jì)算最終路徑，還需在這個(gè)表中添加表示父節(jié)點(diǎn)的列前普。父節(jié)點(diǎn)的意思是該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
節(jié)點(diǎn)：父節(jié)點(diǎn)
黑膠唱片：樂譜
海報(bào)：樂譜
吉他：未知
架子鼓：未知
鋼琴：未知
第一步：找出最便宜的節(jié)點(diǎn)肚邢。在這里，換海報(bào)最便宜拭卿。還有更便宜的換海報(bào)的途徑嗎道偷？
這一點(diǎn)非常重要，我們來想一想记劈，我們的R能夠通過一系列交換得到海報(bào)勺鸦，還能額外得到錢嗎？答案是不能目木，因?yàn)楹?bào)是R能夠到達(dá)的最便宜的節(jié)點(diǎn)换途，沒法再便宜了。下面我們?cè)倥e個(gè)例子刽射，假設(shè)你要從家里去單位军拟。
如果經(jīng)停車場(chǎng)前往學(xué)校，能不能將時(shí)間縮短到少于2分鐘呢誓禁？不可能懈息，因?yàn)橹磺巴＼噲?chǎng)就需要6分鐘。另一方面摹恰。有沒有更快到達(dá)停車場(chǎng)的路呢辫继？有。
這就是狄克斯特拉算法背后的理念：找出圖中最便宜的節(jié)點(diǎn)俗慈，并確保沒有到該節(jié)點(diǎn)的更便宜的路徑姑宽！
回到換鋼琴的例子。換海報(bào)需要支付的額外費(fèi)用最少闺阱。
第二步：計(jì)算前往該節(jié)點(diǎn)的各個(gè)鄰居的開銷炮车。
這里可以理解為：父節(jié)點(diǎn)換節(jié)點(diǎn)的開銷
父節(jié)點(diǎn)：節(jié)點(diǎn)：開銷
樂譜：黑膠唱片：5元
樂譜：海報(bào)：0
海報(bào)：吉他：30
海報(bào)：架子鼓：35
未知：鋼琴：無窮大
因?yàn)槲覀冧撉俚母腹?jié)點(diǎn)還沒有找到，為了便于對(duì)比其他交換例子的開銷，所以這里用無窮大
現(xiàn)在的表中包含低音吉他和架子鼓的開銷瘦穆。這些開銷是用海報(bào)交換他們時(shí)需要支付的額外額外費(fèi)用纪隙，因此父節(jié)點(diǎn)為海報(bào)。這意味著扛或，要到達(dá)低音吉他瘫拣，需要沿從海報(bào)出發(fā)的邊前行，對(duì)架子鼓來說亦是如此告喊。
再次執(zhí)行第一步：下一個(gè)最便宜的節(jié)點(diǎn)是黑膠唱片————需要額外支付5美元。
再次執(zhí)行第二步：更新黑膠唱片的各個(gè)鄰居的開銷：
你更新了架子鼓和吉他的開銷派昧！這意味著經(jīng)“黑膠唱片”前往“架子鼓和“吉他”開銷更低黔姜，因此你將這些樂器的父節(jié)點(diǎn)改為黑膠唱片。
父節(jié)點(diǎn)：節(jié)點(diǎn)：開銷
樂譜：黑膠唱片：5元
樂譜：海報(bào)：0
黑膠唱片：吉他：20
黑膠唱片：架子鼓：25
未知：鋼琴：無窮大
下一個(gè)更便宜的是吉他蒂萎，因此更新其鄰居的開銷秆吵。
父節(jié)點(diǎn)：節(jié)點(diǎn)：開銷
樂譜：黑膠唱片：5元
樂譜：海報(bào)：0
海報(bào)：吉他：30
海報(bào)：架子鼓：35
吉他：鋼琴：40
終于計(jì)算除了用吉他換鋼琴的開銷，將父節(jié)點(diǎn)設(shè)置為吉他五慈。最后纳寂，對(duì)最后一個(gè)節(jié)點(diǎn)——架子鼓做同樣的處理。
父節(jié)點(diǎn)：節(jié)點(diǎn)：開銷
樂譜：黑膠唱片：5元
樂譜：海報(bào)：0
海報(bào)：吉他：30
海報(bào)：架子鼓：35
架子鼓：鋼琴：35
如果用架子鼓換鋼琴泻拦，R需要額外支付的費(fèi)用更少毙芜。因此，采用最便宜的交換路徑時(shí)争拐，R需要額外支付35美元∫钢啵現(xiàn)在我們來確定最終的路徑。當(dāng)前架曹，我們知道最短路徑的開銷為35美元隘冲，但如何確定這條路徑呢？為此绑雄，先中出鋼琴的父節(jié)點(diǎn)展辞。
鋼琴的父節(jié)點(diǎn)為架子鼓，這意味著R需要用架子鼓來換鋼琴因此我們就沿著這一邊万牺。
我們來看看需要沿哪些邊前行罗珍。鋼琴的父節(jié)點(diǎn)為架子鼓。
架子鼓的父節(jié)點(diǎn)為黑膠唱片脚粟。
因此R需要用黑膠唱片來換架子鼓靡砌，顯然，他需要用樂譜來換黑膠唱片珊楼。通過沿父節(jié)點(diǎn)回溯通殃，便得到了完整的交換路徑。：樂譜花5元換黑膠唱片，用黑膠唱片花20元換架子鼓画舌，最后用架子鼓花10元換鋼琴堕担。
新概念：負(fù)權(quán)邊：
在前邊的交換實(shí)例中，A提供了兩種可用樂譜交換的東西曲聂。
假設(shè)黑膠唱片不是A的霹购，而是S的，且S愿意用黑膠唱片和7美元換海報(bào)朋腋。換句話說齐疙，換得A的海報(bào)后，R用它來換S的黑膠唱片時(shí)旭咽，不但不用支付額外的費(fèi)用贞奋，還可得7美元。對(duì)于這種情況穷绵，如何在圖中表示出來呢轿塔？
從黑膠唱片到海報(bào)的邊為負(fù)！現(xiàn)在R有兩種獲得海報(bào)的方式仲墨。
第二種方式更劃算---R可以賺2美元勾缭！你可能還記得，R可以用海報(bào)換架子鼓目养，但現(xiàn)在有兩種換的架子鼓的方式俩由。
1.R可以用樂譜換黑膠唱片再用黑膠唱片換海報(bào)再用海報(bào)換架子鼓---開銷33元
2.R可以用樂譜換海報(bào)再用海報(bào)換架子鼓--開銷35元。
如果你用狄克斯特拉算法來計(jì)算這個(gè)圖癌蚁，R會(huì)選擇錯(cuò)誤的路徑采驻，開銷最多的那條，讓我們來看看對(duì)這個(gè)圖執(zhí)行狄克斯特拉算法的情況匈勋。
首先礼旅，看看開銷表：
黑膠唱片：5
海報(bào)：0
架子鼓：無窮大（再說一遍，因?yàn)闆]有更新它的父節(jié)點(diǎn)）
接下來洽洁，找出開銷最低的節(jié)點(diǎn)痘系，并更新其鄰居的開銷。在這里饿自，開銷最低的節(jié)點(diǎn)是海報(bào)汰翠，我們來更新其鄰居的開銷
黑膠唱片：5
海報(bào)：0
架子鼓：35（此時(shí)架子鼓的父節(jié)點(diǎn)是海報(bào)）
現(xiàn)在架子鼓的開銷變成了35
我們來找出最便宜的未處理的節(jié)點(diǎn)（目前只有兩個(gè)父節(jié)點(diǎn)：黑膠唱片和海報(bào)，但是海報(bào)已經(jīng)處理了昭雌，所以現(xiàn)在我們來處理黑膠唱片）##記赘椿健！這里海報(bào)的節(jié)點(diǎn)已經(jīng)更新了Ｖ蛭浴佛纫！
更新黑膠唱片的節(jié)點(diǎn)：唯一的鄰居——海報(bào)已經(jīng)被處理了，也就是在計(jì)算機(jī)里已經(jīng)把海報(bào)這個(gè)鄰居刪除了，所以我們發(fā)現(xiàn)黑膠唱片沒有鄰居呈宇，因此算法到此結(jié)束好爬，開銷如下：
換的架子鼓的開銷為35。你知道有一種交換方式只需要33甥啄，但狄克斯特拉算法沒有找到存炮。這是因?yàn)榈铱怂固乩惴ㄟ@樣假設(shè)：對(duì)于處理過的海報(bào)節(jié)點(diǎn)，沒有前往該節(jié)點(diǎn)的更短路徑蜈漓。這種假設(shè)僅在沒有負(fù)權(quán)邊時(shí)才成立穆桂。因此，不能將狄克斯特拉算法用于包含負(fù)權(quán)邊的圖融虽。
那么本期先到這里 下一期用Python實(shí)現(xiàn)狄克斯特拉算法
感謝大家的閱讀 謝謝大家享完！
