（一）迪杰斯特拉算法（時(shí)間復(fù)雜度O(n2)）
迪杰斯特拉（Dijkstra）算法是求某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑，這是一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法。
首先引進(jìn)一個(gè)輔助向量D,它的每個(gè)分量D[i]表示當(dāng)前所找到的從始點(diǎn)v到每個(gè)終點(diǎn)vi的最短路徑的長(zhǎng)度。它的初態(tài)為：若從v到vi有弧，則D[i]為弧上的權(quán)值；否則置D[i]為無(wú)窮大。顯然，長(zhǎng)度為D[j]=Min{D[i]|vi屬于V}的路徑就是從v出發(fā)的長(zhǎng)度最短的一條最短路徑。因此，在一般情況下，下一條長(zhǎng)度次短的最短路徑的長(zhǎng)度必為D[j]=Min{D[i]|vi 屬于 V-S} 其中D[i]或者為?。╲,vi)上的權(quán)值，或者是D[k](vk屬于S)和?。╲k,vi）上的權(quán)值之和。算法步驟如下：
(1)假設(shè)用帶權(quán)的鄰接矩陣arcs來(lái)表示帶權(quán)有向圖，arcs[i][j]表示弧(vi,vj)上的權(quán)值。若(vi,vj)不存在，則置arcs[i][j]為無(wú)窮大。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)（終點(diǎn)）vi,可能達(dá)到的最短路徑長(zhǎng)度的初值為：
D[i]=G.arcs[v][vi],vi屬于V
(2)選擇Vj，使得
D[j]=Min{D[i]|vi 屬于V-S}
vj 就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)。令
S=SＵ?。辏?br />(3) 修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度。如果D[j]+arcs[j][k]<D[k]則修改D[k]為 D[k]=D[j]+arcs[j][k]
(4) 重復(fù)操作(2),(3)共 n-1次。由此求得從v到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。
（二）弗洛伊德(Floyd)算法（時(shí)間復(fù)雜度為O(n3)）
弗洛伊德（Floyd）算法是求圖中每一對(duì)頂點(diǎn)之間的最短路徑，時(shí)間復(fù)雜度為O(n3).
弗洛伊德算法仍從圖的帶權(quán)鄰接矩陣cost出發(fā)，其基本思想是 :
假設(shè)求從頂點(diǎn)vi到vj的最短路徑。如果從vi到vj有弧，則從vi到vj存在一條長(zhǎng)度arcs[i][j]的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。首先考慮路徑(vi,v0,vj)是否存在（即判別弧（vi,v0）和(v0,vj)是否存在)。 如果存在，則比較(vi,vj)和(vi,v0,vj)是否存在(即判別弧(vi,v0)和(v0,vj)是否存在).如果存在，則比較(vi,vj)和(vi,v0,vj)的路徑長(zhǎng)度取長(zhǎng)度較短者為從vi到vj的中間頂點(diǎn)的序號(hào)不大于0的最短路徑。假如在路徑上再增加一個(gè)頂點(diǎn)v1,也就是說(shuō)，如果(vi,...v1)和(v1...vj)分別為當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于0的最短路徑，那么（vi,...,v1,...vj）就有可能是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑。將它和已經(jīng)得到的從vi到vj中間的頂點(diǎn)序號(hào)不大于0的最短路徑相比較，從中選出中間頂點(diǎn)的序號(hào)不大于1的最短路徑之后，再增加一個(gè)頂點(diǎn)v2,繼續(xù)進(jìn)行試探。依次類推。在一般情況下，若(vi,...,vk)和(vk,...vj)分別是從vi到vk和從vk到vj的中間頂點(diǎn)的序號(hào)不大于k-1的最短路徑，則將(vi,...vk,...vj)和已經(jīng)得到的從vi到vj且中間頂點(diǎn)序號(hào)不大于k-1的最短路徑相比較，其長(zhǎng)度較短者便是從vi到vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑。這樣，在經(jīng)過(guò)n次比較后，最后求得的必是從vi到vj的最短路徑。
現(xiàn)定義一個(gè)n階方陣序列
D(-1),D(0),D(1),...D(k),...D(n-1)
其中
D(-1)[i][j]=G.arcs[i][j].
D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]} 0<=k<=n-1
從上述計(jì)算公式可見(jiàn)，D(1)[i][j]是從vi到vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑的長(zhǎng)度。D(k)[i][j]是從vi到vj的中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度。D(n-1)[i][j]就是從vi到vj的最短路徑的長(zhǎng)度。