『壹』 Dijkstra演算法
迪傑斯特拉演算法（Dijkstra）是由荷蘭計算機科學家狄克斯特拉在1959年提出的。它是一種求解有權圖中最短路徑的演算法，主要特點是採用貪心演算法的策略，從起始點開始，每次遍歷到距離始點最近且未訪問過的頂點的鄰接節點，直到擴展到終點為止。
迪傑斯特拉演算法求的是單源最短路問題。其實現過程如下：
示例中我們可以發現，這里的迪傑斯特拉演算法只適用於邊權均為正的圖。Dijkstra模板題如下：
給定一個有n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。請你求出1號點到n號點的最短距離，如果無法從1號點走到n號點，則輸出-1。輸入格式：第一行包含整數n和m。接下來m行每行包含三個整數x，y，z，表示存在一條從點x到點y的有向邊，邊長為z。輸出格式：輸出一個整數，表示1號點到n號點的最短距離。如果路徑不存在，則輸出-1。數據范圍：[公式]，[公式]，圖中涉及邊長均不超過10000。輸入樣例：3 3 1 2 2 2 3 1 1 3 4 輸出樣例：3
分析：由本題的點和邊的數據范圍可知，這是一個稠密圖，因此使用鄰接矩陣來存儲圖。（樸素Dijkstra正是用來處理稠密圖的）注意：本題有重邊和自環。由於邊權為正，所以自環一定不會在最短路中。而對於重邊，我們存下最短邊即可。
代碼實現：時間復雜度為[公式]。對於稀疏圖（m與n數據范圍接近時），Dijkstra還有另外一種形式：堆優化Dijkstra。優化主要在尋找距離最小的點的操作上。堆有兩種實現方式，之前已經有寫過手寫堆，這里使用另外一種堆的實現方式：優先隊列。由於是稀疏圖，存儲方式需要改成鄰接表形式。其思路和樸素Dijkstra一致。
代碼實現：時間復雜度為[公式]。
以上就是樸素Dijkstra演算法和堆優化Dijkstra演算法。都是用於單源正權邊最短路。未必優化版的就是更好的，樸素版適合稠密度，堆優化版適合稀疏圖。
『貳』 用Dijkstra演算法求圖中從頂點a到其他各頂點間的最短路徑，並寫出執行演算法過程中各步的狀態。
迪克斯加（Dijkstra）演算法(最短路徑演算法)是由荷蘭計算機科學家艾茲格·迪科斯徹發現的。演算法解決的是有向圖中任意兩個頂點之間的最短路徑問題。
舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離。 迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
迪科斯徹演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。 我們以V表示G中所有頂點的集合。 每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。 我們以E所有邊的集合，而邊的權重則由權重函數w: E → [0, ∞]定義。 因此，w(u,v)就是從頂點u到頂點v的非負花費值(cost)。 邊的花費可以想像成兩個頂點之間的距離。任兩點間路徑的花費值，就是該路徑上所有邊的花費值總和。 已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低花費路徑(i.e. 最短路徑)。 這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑
這個演算法是通過為每個頂點v保留目前為止所找到的從s到v的最短路徑來工作的。初始時，源點s的路徑長度值被賦為0（d[s]=0）， 同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑（對於V中所有頂點v除s外d[v]= ∞）。當演算法結束時，d[v]中儲存的便是從s到v的最短路徑，或者如果路徑不存在的話是無窮大。 Dijstra演算法的基礎操作是邊的拓展：如果存在一條從u到v的邊，那麼從s到v的最短路徑可以通過將邊(u,v)添加到尾部來拓展一條從s到u的路徑。這條路徑的長度是d+w(u,v)。如果這個值比目前已知的d[v]的值要小，我們可以用新值來替代當前d[v]中的值。拓展邊的操作一直執行到所有的d[v]都代表從s到v最短路徑的花費。這個演算法經過組織因而當d達到它最終的值的時候每條邊(u,v)都只被拓展一次。
演算法維護兩個頂點集S和Q。集合S保留了我們已知的所有d[v]的值已經是最短路徑的值頂點，而集合Q則保留其他所有頂點。集合S初始狀態為空，而後每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小的d值的頂點。當一個頂點u從Q中轉移到了S中，演算法對每條外接邊(u,v)進行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找權值最小的點為node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各點的權值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.