圖_最短路徑（個(gè)人認(rèn)為應(yīng)該叫最佳路徑）
最短路徑其實(shí)說的是權(quán)重，請仔細(xì)理解權(quán)重的意義夯辖。在實(shí)際應(yīng)用中订框，權(quán)重可以是消耗的時(shí)間南誊、金錢励堡、距離甚至是概率等等，我們求最短路徑讥裤，也就是求這些權(quán)重之和的最姓病（或最大）值
北京地鐵復(fù)雜的線路圖，從育新小區(qū)到公益西橋有很多條線路可以選擇涌乳，從時(shí)間蜻懦、距離、還有車費(fèi)等不同的角度考慮夕晓，可能獲得的最佳線路都不一樣～～～
迪杰斯特拉(Dijkstra)算法
（兩個(gè)頂點(diǎn)之間的最短路徑）
按照路徑長度遞增的產(chǎn)生最短路徑的算法宛乃，也就是說不是一次性算出兩個(gè)定點(diǎn)之間的最短距離，而是通過計(jì)算每個(gè)中間頂點(diǎn)的最短距離蒸辆，最后推導(dǎo)出要求的頂點(diǎn)最短距離
- 5~12行是初始化階段征炼，final一維數(shù)組值均為0，D數(shù)組記錄所有頂點(diǎn)到v0的最短路徑值躬贡，當(dāng)前是{65535,1,5,65535,65535,65535,65535,65535,65535}谆奥，p數(shù)組全為0，表示目前還沒有找到任意一個(gè)頂點(diǎn)的最短路徑
- 13行是一個(gè)主循環(huán)拂玻，每循環(huán)一次求得v0與一個(gè)頂點(diǎn)的最短路徑酸些，也就是讓一個(gè)頂點(diǎn)的final值為1
- 16～24行的循環(huán)宰译，先令min為65535，通過w循環(huán)魄懂，與D[w]比較沿侈，找到目前最小的min和k值。當(dāng)前是：D[1]的值最小市栗，因?yàn)樵诘谝淮纬跏蓟臅r(shí)候缀拭，v0連接的就兩條邊，v1和v2肃廓，如果是第二次循環(huán)智厌，那就是D[2]
- 25～32行，是在修正之前已經(jīng)判定的v0和某個(gè)點(diǎn)的最短距離盲赊，例如：在初始化的時(shí)候v0到v2的最短距離是5铣鹏，但是第一次循環(huán)完成之后，發(fā)現(xiàn)v0->v1＝min=1,v1->v2=3哀蘑，因此v0->v1->v2=min+G.matirx[v1][v2]=4诚卸，這個(gè)值是小于D[2]=5的
佛洛伊德（floyd）算法
能計(jì)算出北京地鐵所有站與站之間在時(shí)間上的最佳路徑，那所有上班族就知道該怎么換乘才最省時(shí)間；媲ā：夏纭！
(所有頂點(diǎn)到其他頂點(diǎn)之間的最短距離)
上面這個(gè)公式的含義就是：我們要判斷所有頂點(diǎn)經(jīng)過k頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)的最短路徑缀台。例如：v->w > v->k->w棠赛，整個(gè)算法就是根據(jù)這個(gè)簡單的邏輯推導(dǎo)出所有頂點(diǎn)到其他頂點(diǎn)的最短路徑，看看下面的圖：
代碼
該算法用一個(gè)三層的循環(huán)遍歷了所有的頂點(diǎn)膛腐，并計(jì)算出了頂點(diǎn)與頂點(diǎn)之間的最短距離
其中: k代表中轉(zhuǎn)頂點(diǎn)睛约、v代表起始點(diǎn)、w代表結(jié)束頂點(diǎn)
可以通過下面的圖形理解k,v,w是怎么運(yùn)作的
這是v0作為中轉(zhuǎn)頂點(diǎn)時(shí)哲身，其他所有頂點(diǎn)通過它到結(jié)束點(diǎn)的最短路徑辩涝，發(fā)現(xiàn)不需要更新
這是v1作為中轉(zhuǎn)頂點(diǎn)，可以看出勘天，例如：原來v0->v2=5怔揩，而現(xiàn)在v0->v1->v2=1+3=4，因此我們就需要改變v0->v2的最短路徑為4脯丝，其他的同理商膊。
就如同上面兩步一樣，循環(huán)進(jìn)行直到所有頂點(diǎn)被處理一邊巾钉，最后結(jié)束得到的就是所有頂點(diǎn)到頂點(diǎn)之間的最短路徑
