基本定义
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
原理
1.首先，引入一个辅助向量D，它的每个分量D[i]表示当前所找到从起始点v（即点V）到其他每个定点vi的长度。
例如，D[3]=2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
2.D的初始状态为：若从v到v1有弧（即从v到vi存在连接边），则D[i]为弧上的权值（即为从v到vi的边的权值）；否则置D[i]为∞。
显然，长度为D[j]=Min{D|vi∈V}的路径就是从v出发到顶点vj的长度最短的一条路径，此路径为(v,vj)。
3.那么，下一条长度次短的是哪一条呢？也就是找到从源点v到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点v到顶点vj的最短路径长度。
假设该次短路径的终点是vk，则可想而知，这条路径要么是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]加上从vj到vk的弧上的权值。
4.一般情况下，假设S为已求得的从源点v出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为x）要么是弧(v,x)，或者是从源点v出发的中间只经过S中的顶点而最后到达顶点x的路径。
因此，下一条长度次短的的最短路径长度必是D[j]=Min{D[i]vi∈V-S}，其中D[i]要么是弧(v,vi)上的权值，或者是D[k]vk(∈S)和弧(vk,vi)上的权值之和。
算法描述如下：
1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的长度的初值为D=arcs[LocateVex(G,vi]，vi∈V；
2）选择vj，使得D[j]=Min{D|vi∈V-S}；
3）修改从v出发的到集合V-S中任一顶点vk的最短路径长度。
问题描述
在无向图G=(V,E)中，假设每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短值。
算法思想
按路径长度递增次序产生算法：
把顶点集合V分成两组：
（1）S：已求出的顶点的集合（初始时只含有源点V0）
（2）V-S=T：尚未确定的顶点集合
将T中顶点按递增的次序加入到S中，保证：
（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
（反证法可证）
求最短路径步骤
算法步骤如下：
G={V,E}
1.初始时令S={V0},T=V-S={其余顶点}，T中顶点对应的距离值
若存在，d(V0,Vi)为弧上的权值
若不存在，d(V0,Vi)为∞
2.从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
堆优化
思考
该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。
实现
1.将与源点相连的点加入堆，并调整堆。
2.选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
3.处理与u相邻的，未被访问过的，满足三角不等式的顶点。
1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
2):若该点不在堆里，加入堆，更新堆。
4.若取到的u为终点，结束算法；否则重复步骤2、3。
