djstra算法原理？

迪杰斯特拉算法的原理

首先引入一個(gè)輔助向量D，它的每個(gè)分量D[i]代表當(dāng)前找到的運(yùn)行動(dòng)畫(huà)過(guò)程的Dijkstra算法從起點(diǎn)(即源點(diǎn))到其他每個(gè)頂點(diǎn)的長(zhǎng)度。例如，D[3] 2意味著從起點(diǎn)到頂點(diǎn)3的路徑的相對(duì)最小長(zhǎng)度是2。這里強(qiáng)調(diào)的相對(duì)性，是指在算法執(zhí)行的過(guò)程中，d的值向最終結(jié)果逼近，但不一定等于過(guò)程中的長(zhǎng)度。

②D的初始狀態(tài)是:如果V到v[i]有一條弧(即V到v[i]有一條連接邊)，那么D[i]就是弧上的權(quán)(即V到v[i]的邊的權(quán))；否則，設(shè)D[i]為∞。顯然，長(zhǎng)度為D[j] Min{ D |v[i]∈V}的路是從V到頂點(diǎn)v[j]的最短路徑，即(V，v[j])。

那么，下一個(gè)長(zhǎng)度最短的是哪一個(gè)？即找到從源點(diǎn)V到下一個(gè)頂點(diǎn)的最短路徑長(zhǎng)度對(duì)應(yīng)的頂點(diǎn)，這個(gè)最短路徑長(zhǎng)度僅次于從源點(diǎn)V到頂點(diǎn)v[j]的最短路徑長(zhǎng)度。假設(shè)這個(gè)短路徑的終點(diǎn)是v[k]，可以想象這個(gè)路徑不是(v，v[k])就是(v，v[j]，v[k])。它的長(zhǎng)度要么是從V到v[k]的弧上的重量，要么是從v[j][k]的弧上的重量。

(4)一般情況下，假設(shè)S是從源點(diǎn)V開(kāi)始的最短路徑長(zhǎng)度的頂點(diǎn)的集合，可以證明下一條最短路徑(假設(shè)它的終點(diǎn)是X)或者是一條弧(V，X)或者是從源點(diǎn)V開(kāi)始，只經(jīng)過(guò)S中的頂點(diǎn)，最后到達(dá)頂點(diǎn)的路徑。因此，下一個(gè)最短路徑長(zhǎng)度必須是D[j] Min{ D[i] |v[i]∈V-S}，其中D是弧上的權(quán)重(V，v[i])或D[i]( v[k]∈S)和弧。

編程里面，怎么求最短路徑? 只求方法不要代碼？

設(shè)A點(diǎn)到B點(diǎn)的距離為xA到點(diǎn)C Y，C點(diǎn)到B點(diǎn)的距離為z，如果xgty z，則更新A點(diǎn)到B點(diǎn)的距離為y z .這叫松弛運(yùn)算Dijkstra算法:初始設(shè)置low[i]dis[A][i] mark A .對(duì)于每個(gè)剩余的點(diǎn)，找出最小的未標(biāo)記的low[k] mark K .對(duì)于與k相連的每個(gè)點(diǎn)J，執(zhí)行松弛運(yùn)算low [j] min (dis