最短路徑
- 網(wǎng)圖：
兩個頂點(diǎn)之間經(jīng)過的邊上權(quán)值之和最小的路徑股毫；
迪杰斯特拉（Dijkstra）算法
- 按照路徑長度遞增的產(chǎn)生最短路徑献宫；
- 不是一次性算出兩個定點(diǎn)之間的最短距離忽孽；
- 通過計(jì)算每個中間頂點(diǎn)的最短距離硝皂，最后推導(dǎo)出要求的頂點(diǎn)最短距離顷窒；
graph-matrix
graph-Dijkstra_code1
graph-Dijkstra_code2
- 5~12行是初始化階段蛙吏，final一維數(shù)組值均為0，D數(shù)組記錄所有頂點(diǎn)到v0的最短路徑值，當(dāng)前是{65535,1,5,65535,65535,65535,65535,65535,65535}鸦做，p數(shù)組全為0璧疗，表示目前還沒有找到任意一個頂點(diǎn)的最短路徑
- 13行是一個主循環(huán)，每循環(huán)一次求得v0與一個頂點(diǎn)的最短路徑馁龟，也就是讓一個頂點(diǎn)的final值為1
- 16～24行的循環(huán)崩侠，先令min為65535，通過w循環(huán)坷檩，與D[w]比較却音，找到目前最小的min和k值。當(dāng)前是：D[1]的值最小矢炼，因?yàn)樵诘谝淮纬跏蓟臅r候系瓢，v0連接的就兩條邊，v1和v2句灌，如果是第二次循環(huán)夷陋，那就是D[2]
- 25～32行，是在修正之前已經(jīng)判定的v0和某個點(diǎn)的最短距離胰锌，例如：在初始化的時候v0到v2的最短距離是5骗绕，但是第一次循環(huán)完成之后，發(fā)現(xiàn)v0->v1＝min=1,v1->v2=3资昧，因此v0->v1->v2=min+G.matirx[v1][v2]=4酬土，這個值是小于D[2]=5的
