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