Dijkstra概念
要找出最短路径，其实就是从起点遍历所有能到达的顶点，然后计算他们的权重。Dijkstra算法核心在于边的松弛（relax），可以想象成一根绷紧的橡皮筋，让它放松下来。即是计算源点(s)经过当前点(v)到目标点(w)的权重，如果比目标点(w)之前的权重要小，就替换掉。最终的结果就是生成一颗最小路径树。这个算法和prim算法非常相似，甚至就是prim即时算法的变种。如果加权无向图和加权有向图的边和权重对应，最短路径树和最小生成树其实是等价的。
Dijkstra算法并不能处理权重为负数的边。
例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
2.D的初始状态为：若从
到
有弧（即从
到
存在连接边），则D
为弧上的权值（即为从
到
的边的权值）；否则置D
为∞。
显然，长度为 D
= Min{ D |
∈V } 的路径就是从
出发到顶点
的长度最短的一条路径，此路径为(
)。
3.那么，下一条长度次短的是哪一条呢？也就是找到从源点
到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点
到顶点
的最短路径长度。
假设该次短路径的终点是
，则可想而知，这条路径要么是(
)，或者是(
)。它的长度或者是从
到
的弧上的权值，或者是D
加上从
到
的弧上的权值。
4.一般情况下，假设S为已求得的从源点
出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为
）要么是弧(
)，或者是从源点
出发的中间只经过S中的顶点而最后到达顶点
的路径。
因此，下一条长度次短的的最短路径长度必是D
= Min{ D
|
∈V-S }，其中D
要么是弧(
)上的权值，或者是D
(
∈S)和弧(
,
)上的权值之和。
算法描述如下：
1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从
出发的的终点的集合，初始状态为空集。那么，从
出发到图上其余各顶点
可能达到的长度的初值为D=arcs[Locate Vex(G,
)]，
∈V；
2）选择
，使得D
=Min{ D |
∈V-S } ；
3）修改从
出发的到集合V-S中任一顶点
的最短路径长度。
按路径长度递增次序产生算法：
把顶点集合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中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W，加入到S中
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止
版权声明：本文为kevin6666原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。