-- 贪婪技术的一种经典算法，戴克斯特拉算法（维基说法）
# 算法逻辑
算法描述 Dijkstra (G, s)
// 单起点最短路径的Dijstra算法
// 输入: 具非负权重加权连通图 G = < V, E> 以及它的顶点s
// 输出: 对于V中的每一个顶点v来说, 从s到v的最短路径的长度dv
// 以及路径上的倒数第二个顶点pv
Initialize(Q) // 将顶点优先队列初始化为空
for V中每一个顶点 v do
dv = -1; pv = null;
Insert(Q, v, dv); // 初始化优先队列中顶点的优先级
ds = 0; Decrease(Q, s, ds);
Vt = {} // 初始化为空
for i = 0 to |V| - 1 do
u* = DeleteMin(Q); //删除优先级最小的元素
Vt = Vt + { u* };
for V - Vt 中每一个和u*相邻的顶点u do
if du* + w(u*, u) < du
du = du* + w(u*, u);
pu = u*;
Decrease(Q, u, du);
# 算法效率
分析该算法的时间复杂度，假设对应的连通图边数 m 和顶点数 n 。
1， 最简单实现方法，以一个链表或者数组来存储所有顶点的集合Q，而搜索Q中权值最小元素操作DeleteMin只需线性搜索为复杂度O(n)。该算法整体的时间复杂度是 O(n^2)。
2， 用邻接表来更有效的实现该算法，同时以二叉树结构作为优先队列存Q，则搜索权值最小元素DeleteMin时间复杂度为Q(log n)，此时该算法整体的时间复杂度为O((m + n)log n)，
# 示例说明
（还是伪码，从代码提炼出来的伪码，这样看起来应该比较浅显易懂。）
void Dijkstra (Graph& G)
{
Queue Q; Path P;
InitQueuePath(Q, P);
for (int s=0; s< G.points;s++) {
Decrease(Q, s, 0);
for (int i=0; i < G.points-1; i++) {
int u = DeleteMin(Q, G.flag, G.points);
if (u==-1)
break;
for (int j=0; j< G.points; j++) {
if ( G.flag[j]==false && ((__int64)Q[u]+G.A[u][j])<Q[j]) {
P[j] = u;
Decrease(Q, j, Q[u]+G.A[u][j]);
}
}
}
for (int i=0; i < G.points; i++)
G.A[i][s] = G.A[s][i] = Q[i];
}
}
完整的C++示例代码存放在github。
# 引用扩展
参见维基上伪码描述如下：
在下面的算法中，u := Extract_Min(Q) 在顶点集合 Q 中搜索有最小的 d[u] 值的顶点 u。这个顶点被从集合 Q 中删除并返回给用户。
function Dijkstra(G, w, s)
for each vertex v in V[G] // 初始化
d[v] := infinity // 将各点的已知最短距离先设置成无穷大
previous[v] := undefined // 各点的已知最短路径上的前趋都未知
d[s] := 0 // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
S := empty set
Q := set of all vertices
while Q is not an empty set // Dijkstra演算法主體
u := Extract_Min(Q)
S.append(u)
for each edge outgoing from u as (u,v)
if d[v] > d[u] + w(u,v) // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
d[v] := d[u] + w(u,v) // 更新路径长度到更小的那个和值。
previous[v] := u // 记录前趋顶点
for each vertex v in V[G] // 初始化
d[v] := infinity // 将各点的已知最短距离先设置成无穷大
previous[v] := undefined // 各点的已知最短路径上的前趋都未知
d[s] := 0 // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
S := empty set
Q := set of all vertices
while Q is not an empty set // Dijkstra演算法主體
u := Extract_Min(Q)
S.append(u)
for each edge outgoing from u as (u,v)
if d[v] > d[u] + w(u,v) // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
d[v] := d[u] + w(u,v) // 更新路径长度到更小的那个和值。
previous[v] := u // 记录前趋顶点
如果我们只对在 s 和 t 之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足 u = t 的话终止程序。
通过推导可知，为了记录最佳路径的轨迹，我们只需记录该路径上每个点的前趋，即可通过迭代来回溯出 s 到 t 的最短路径（当然，使用后继节点来存储亦可。但那需要修改代码）：
s := empty sequence
u := t
while defined u
insert u to the beginning of S
u := previous[u] //previous数组即为上文中的p
现在序列 S 就是从 s 到 t 的最短路径的顶点集。
