简谈迪克斯特拉算法

一直想要学点简单的算法，叨叨了好久，开始吧【这篇文章的前言无非就是我想说点废话，大家可以选择性的过滤哈。】

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家 狄克斯特拉 于1959 年提出的，因此又叫 狄克斯特拉算法 。是从一个顶点到其余各顶点的 最短路径 算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

敲黑板~进入正题

迪杰斯特拉算法是目前 OIER 们最爱用的最短路算法，下面讲一下这个算法的思路【图丑，请大家忍耐一下】：

第一步，我们先把a加入集合，数组变成（s = {a}, dis[] = {0, ∞,∞,∞,∞,∞,∞,∞}）

第二步，找到和a最近的点，为b，把b加入集合，并确定他的最短路径【要注意箭头方向哈仿歼塌】，数组变成（s = {a, b}, dis[] ={0,2,∞,∞,∞,∞,∞,∞}）

第三步，找到和b最近的点，为d，把d加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d}, dis[] = {0,2,∞,3,∞,∞,∞,∞}）

第四步，找到和d最近的点，为e，把e加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e}, dis[] = {0,2,∞,3,5,∞,∞,∞改纤}）

第五步，找到和e最近的点，为f，把f加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f}, dis[] = {0,2,∞,3,5,9,∞,∞}）

第六步，找到和f最近的点，为g，把g加入集合，并确定他的最短路径【要注意箭头方向】，数组变成（s = {a, b, d, e, f, g}, dis[] = {0,2,∞,3,5,9,12,∞}）

第七步，目前只剩下c和h了，那么我们先要找到距离集合路径最短的c，把c加备圆入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g}, dis[]= {0,2,13,3,5,9,12,∞}）

第八步，最后一步，我们找到距离集合路径最短的h，把h加入集合，并确定他的最短路径，数组变成（s = {a, b, c, d, e, f, g, h}, dis[] = {0,2,13,3,5,9,12,18}）

得嘞，这个大致的思路是这样的，还有后续哟，欲知后事如何，请看下回讲解~

我们老师给的标准程序，我原封不动送给你吧，系统地讲最短路问题的，要用在你的矩阵的情况的话记得把你里面0全改成inf，耐心看吧，阐述得很完整了，绝对是个高效的算法：

Dijkstra算法

Edser Dijkstra 是荷兰计算机科学家，于1959年发表了Dijkstra算法，时年29岁. 这算法计算具有非负权的N阶矩阵W的图上从源点S（Source）, S(1..N), 出发到达所有各点K, K=1..N, 的最短路。（Edward F. Moore 在1957年也得到类似的算法）.

算法

1. 对每个点I指定一个离点S的距离初始值L(I). 在始点S的值为零, 即L(S)=0，其它点的值为Inf.

2. 所有的点标记为未走访的. 置始点S为当前点C.

3. 对于当前点C, 考虑它的所有未走访的相邻点J, 并更新J的距离值为

L(J)=min(L(J), L(C)+W(C,J))

4. 把当前点C标记为走访过的点. 走访过的点C的距离L(C)就是点S到C的最短距离, 而且以后不再检查走访过得点了.

5. 如果所有的点都是走访过的点, 完成. 不然, 把未走访的点中具有最小距离值的点作为下一个当前点C, 转步骤3.

编制程序的要求: 给定N阶非负权矩阵W, W(I,J)是从点I到点J的距离, W(I,I)的值可以赋以任意值(比较方便的是裂埋好赋以Inf). 如果只需求源点S(Source)到达指定的终点T(Target)，给出最短路径Z及其长度L(T)如果不指定终点T时，Z是一个N维行向量，Z(K)表示S点到K点的最短路上K点的前一点, Z(S)=0, L是一个N维行向量, L(K)是S点到K点的最短距离. 如果不给出源点S及终点T, 则默认源点S=1, 按不指定终点的肆铅情况办.

MATLAB函数子程序dijkstra.m为:

function [L,Z]=dijkstra(W,S,T)

%用 Dijkstra 算法求最短路,W(I,J)是从点 I 到点 J 的距离, W(I,I)=0,I,J=1..n点 I 和点 J 无边直接相连时,W(I,J)=inf.

% L表示从始点 S 到终点 T 的最短距离, Z 表示点 S 到 T 的一条最短路径. 当不给出终点 T 时，L(J)表示从点 S 到点 J 的最短距离, J=1..nZ(I)表示最短路径上点 I 的前一点(父亲点),

% 可由 Z 追溯最短路径，当不给液知出起点 S 及终点 T 时默认 S = 1 及按不指定终点的情况办.

if nargin<2 S=1T=0elseif nargin<3 T=0end%如只给出W, 默认始点 S=1算出S到所有点的距离如没给出终点, 算出S到所有点的距离

N=length(W(:,1))%顶点数

L=Inf*ones(1,N),L(S)=0%L赋初值，在S点为0，其它点为Inf

C=S%当前点为始点S

Q=1:N% 未走访的顶点集

Z=S*ones(1,N)Z(S)=0% Z赋初值,因始点 S 无父亲点,故把 S 点的Z值改为0

for K=1:N % 更新 L 和 Z 的循环

Q=setdiff(Q,C)%当前点 C 未走访的点集

[L(Q),ind]=min([L(Q)L(C)+W(C,Q)])%当前点C已走访了所有的相邻的未走访的点，更新 L

Z(Q(find(ind==2)))=C%更新Z, 至此C已是走访过的点了

if T&C==T %若 C 点是终点 T, 不用再计算到其它未走访的点的最短路

L=L(T)%最短路长；

road=T%最短路径终点；

while T~=S%追溯最短路径上的点

T=Z(T)road=[road,T]

end

Z=road(length(road):-1:1)%颠倒次序；

return

end

[null, mC]=min(L(Q))

if null==Inf

disp('到值是Inf的点的路不通！')Z(find(L==Inf))=nanreturn

else

C=Q(mC)% 把未走访的点集Q中与始点距离最近的点作为新的当前点C

endend

Dijkstra算法的证明：

以下实质上是用动态规划思想的证明.

记第 K 阶段开始时考虑的当前点为C(K），则第 K 阶段完成时确定的当前点为C(K+1)，记集合P(K)={C(1),C(2),…,C(K)}, 记 Q(K)为 P(K) 的余集. 我们来证明对于每个点V∈P(K), L(V)是从源点S到点V点的最短路的长度， K=1..N.

证明：对 K 施行数学归纳法，当 K=1 时， P(1)={S}, V=S, L(V)=0, 命题真设对于K=M, M≥1, N≥M时命题真, 即当V∈P(M)时， L(V)是S到V的最短路的长度. 由于P(M+1)=P(M)∪{C(M+1)}, 所以只要证明 L(C(M+1))是点S到C(M+1)点的最短路的长度. 记 R:=C(1)..C(M+1) 是从 S=C(1) 到 C(M+1)的任意一条路， 记L(C(J)I)为在K=I阶段, J>I时更新的L(C(J))的值. 则从 S 出发沿路 R 往 C(M+1)走时, 必存在第一条边(C(I),C(J))使得C(I)∈P(M)，C(J)∈Q(M). 由归纳假设, 这条路 R 的长度W(R)≥L(C(I))+W(C(I),C(J))+W(C(J)..C(M+1))

≥L(C(I))+W(C(I),C(J)).

按算法,在第K=I阶段完成时，L(C(I))+W(C(I),C(J))≥L(C(J)I). 因I≤M, 故L(C(J)I)≥L(C(J)M), 从而W(R)≥L(C(J)M). 由算法, L(C(M+1))≤L(C(J)M)故W(R)≥L(C(M+1)) 另外按算法, 确有长度等于L(C(M+1))的一条路径, 证毕.

---