数据结构与算法：Dijkstra算法

Dijkstra算法用于图中计算最小路径，在路由选择中也有用到。以一个图为例：

算法执行过程：

1、选择一个起始点，并初始化其他各个点到起始点的开销表D以及相对应的上一个点（初始化时就是起点）。
2、 找到开销表D中的最小值，选择这个开销表的最小值所对应的点作为下一个节点，记作ｐ，并更新其他未经过的点n到这个点ｐ的开销表D,其中开销表D的数值更新为当前开销表的数值D( n ) 与当前到这个节点ｐ的开销表的数值Ｄ( p )加上p点到当前点的开销路径值的最小值。即:

D(n)=min(D(n),D( p)+c(p,n))

并记下这个最小值所指向的上一个节点，若当前开销表的数值D( p)为最小值，则选择当前D( p)指向的节点（第一次循环时指向的时起始点）。

PS：c ( n , p )记为p点到当前点n的开销路径值。

3、循环第二步，直到遍历完所有的节点。

以上图为例一步步阐述算法执行的过程。

1、首先选择u作为起点，其他各个点到u的开销表为：

已加入节点	D(x)	D(v)	D(w)	D(y)	D(z)
u	1,u	2,u	5,u	∞	∞

表格里的数字为开销表的数值，字母为指向的上一个节点。
2、选择开销表中的最小值作为下一个节点，这里可以看到D(x)=1是最小的，因此选择x作为下一个节点，然后更新其他未经过的点，即y、z、w、v的开销表。各个点的更新过程如下：

对于v： D(v)=2, D(x)+c(x,v)=1+2=3,将D(v)更新为原来的D(v)，仍然指向u。
对于y： D(y)=∞, D(x)+c(x,y)=1+1=2,因此更新将D(y)更新为2, 指向x。
对于w： D(w)=5, D(x)+c(x,w)=1+3=4,因此将D(w)更新为4, 指向x。
对于z： D(z)=∞，D(x)+c(x,z)=∞，D(z)仍为∞，此时不指向u也不指向x,因为是无穷意味着z到x和u都没有路径。

更新完后的开销表为：

已加入节点	D(x)	D(v)	D(w)	D(y)	D(z)
ux		2,u	4,x	2,x	∞

3、继续循环，可以看到上面的表中最小值为D(y)和D(v),这里选择y作为下一个节点。
对于v： D(v)=
对于w：D(w)=4, D(y)+c(y,w)=3，更新D(w)为3，指向y。
对于z： D(z)=∞，D(y)+c(y,z)=4，更新为4，指向y。

更新完后的开销表为：

已加入节点	D(x)	D(v)	D(w)	D(y)	D(z)
uxy		2,u	3,y		4，y

4、继续循环，选择v作为下一次节点，更新开销表。

对于w：D(w)=3, D(v)+c(v,w)=2+3=5,更新为3，仍然指向y。
对于z：D(z)=4,D(v)+c(v,z)=∞,更新为4，仍然指向y。

更新后的开销表为：

已加入节点	D(x)	D(v)	D(w)	D(y)	D(z)
uxyv			3,y		4，y

5、继续循环，选择w作为下一次节点，更新开销表。

对于z： D(z)=4, D(w)+c(w,z)=3+5=8,更新为4，仍然指向y。
更新后的选择表为：

已加入节点	D(x)	D(v)	D(w)	D(y)	D(z)
uxyvw					4，y

6、继续循环，开销表中只剩下z一个数值了，选择z作为下一个节点，将z记作已加入的节点。

此时即找到最小路径，最小路径值即为4，最小路径按照其指向的上一个节点依次：
z→y→x→u。

总结：
Dijkstra算法看似复杂，实际上其核心要点在更新开销表时的比较动作，以第三步中的对于w点为例来说明：

对于w：D(w)=4, D(y)+c(y,w)=3，更新D(w)为3，指向y。

D(w)=4为从起点u→x→w的路径值，而 D(y)+c(y,w)=3则为从起点u→x→y→w的路径值。
这里的两者比较说明从起点u到w，经过后面这条路径更短一些，所以选择后面这条路径作为到w点的最小路径。因此开销表记录的就是起点到各个点的最小路径值。经过循环完所有的点，就可以得到起点到各个点的最小路径。