‘壹’ 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.