1.綜述
 
 　　Dijkstra算法解決的是帶權(quán)重的有向圖上單源最短路徑問題，該算法要求所有邊的權(quán)重都為非負(fù)值。
 
 　　算法重復(fù)從結(jié)點集 V-S中選擇最短路徑估計最小的結(jié)點 u ,將 u 加入到集合 S ,然后對所有從 u 出發(fā)的邊進(jìn)行
 
 　　松弛操作（相當(dāng)于遍歷選出最小權(quán)值）。使用一個最小優(yōu)先隊列 Q 來保存結(jié)點集合。（代碼實現(xiàn)中：設(shè)置一個標(biāo)記數(shù)組）。迪科斯徹算法使用了廣度優(yōu)先搜索算法。算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。sat答案
 
 　　迪克斯拉算法類似于廣度優(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<n;j++）
 
 　　if （（mark[j]==0）&&（minc>=d[j]）） {minc=d[j];w=j;}
 
 　　mark[w]=1;
 
 　　for （j=0;j<n;j++）
 
 　　if （（mark[j]==0）&&（G[w][j]!=infinity）&&（d[j]>d[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)必須非負(fù)
 
 　　頂點標(biāo)號從0開始
 
 　　用如下方法打印路徑：
 
 　　i=t;
 
 　　while （i!=s）
 
 　　{
 
 　　printf（"%d<--",i+1）；
 
 　　i=path[i];
 
 　　}
 
 　　printf（"%d\n",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)前要進(jìn)行松弛的結(jié)點，第三個 for 循環(huán)進(jìn)行松弛操作。
 
 　　3.第三個 for 循環(huán)中的
 
 　　[cpp] view plaincopy在CODE上查看代碼片派生到我的代碼片
 
 　　d[j]>d[w]+G[w][j]
 
 　　其中 d[j] 也包括 d[j] 取值為無窮大的情況，其真實性意義就是 j 點與源點不相連，直接把 d[j] 賦值為當(dāng)前進(jìn)行松弛的點 w 加上 w 到 j 點的權(quán)值。托福答案