1.綜述 Dijkstra算法解決的是帶權(quán)重的有向圖上單源最短路徑問題，該算法要求所有邊的權(quán)重都為非負值。

算法重復(fù)從結(jié)點集 V-S中選擇最短路徑估計最小的結(jié)點 u ，將 u 加入到集合 S ，然后對所有從 u 出發(fā)的邊進行 松弛操作（相當(dāng)于遍歷選出最小權(quán)值）。使用一個最小優(yōu)先隊列 Q 來保存結(jié)點集合。（代碼實現(xiàn)中：設(shè)置一個標(biāo)記數(shù)組）。迪科斯徹算法使用了廣度優(yōu)先搜索算法。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。
迪克斯拉算法類似于廣度優(yōu)先算法，也類似于計算最小生成樹的 Prim 算法。
2.代碼

int?Dijkstra(Graph?G,int?n,int?s,int?t,?int?path[])
{
????int?i,j,w,minc,d[max_vertexes],mark[max_vertexes];
????for?(i=0;i<n;i++)?mark[i]=0;
????for?(i=0;i<n;i++)
????????{?d[i]=G[s][i];
????????path[i]=s;?}
????mark[s]=1;path[s]=0;d[s]=0;
????for?(i=1;i<n;i++)
????????{
???????minc=infinity;
????????w=0;
????????for?(j=0;j=d[j]))?{minc=d[j];w=j;}
????????mark[w]=1;
????????for?(j=0;jd[w]+G[w][j]))
????????????{?d[j]=d[w]+G[w][j];
????????????path[j]=w;?}
????????}
????return?d[t];
}

3.理解 代碼中參數(shù)：

G：

圖，用鄰接矩陣表示

n：

圖的頂點個數(shù)

s：

開始節(jié)點

t：

目標(biāo)節(jié)點

path[]：

用于返回由開始節(jié)點到目標(biāo)節(jié)點的路徑

返回值：

最短路徑長度

注意：

輸入的圖的權(quán)必須非負

頂點標(biāo)號從0開始

用如下方法打印路徑：
i=t;
while (i!=s)
{
printf("%d<--",i+1);
i=path[i];
}
printf("%dn",s+1); ?

1.初始化:先初始化源點 s 的 d[]數(shù)組的值，即把與源點相連的點的權(quán)值賦給 d[] 數(shù)組。 2.用了三個 for 循環(huán)，一個 for 循環(huán)里面鑲嵌兩個并列的 for 循環(huán)。第一個 for 循環(huán)和第二個 for 循環(huán)是找出當(dāng)前要進行松弛的結(jié)點，第三個 for 循環(huán)進行松弛操作。 3.第三個 for 循環(huán)中的?

d[j]>d[w]+G[w][j]

其中 d[j] 也包括 d[j] 取值為無窮大的情況，其真實性意義就是 j 點與源點不相連，直接把 d[j] 賦值為當(dāng)前進行松弛的點 w 加上 w 到 j 點的權(quán)值。
想要理解 Dijkstra 算法的最簡便路徑就是把上面的模板背下來好好理解，背誦是理解的最短路徑。昨天晚上在圖書館寫了一遍 Dijkstra 算法，外加看算法導(dǎo)論理解，從圖書館到宿舍的路上一直在理解 Dijkstra 算法，原來想通一個算法是多么幸福的事。