Dijkstra 算法

最近要给人讲路由，其中的 LS 路由算法其实就是 Dijkstra 的最短路径算法。看了一下，发现这个算法虽然只有短短几行，但讲起来却无比费劲。

我换了个描述方式，看看会不会好一些：

V 是全部点的集合，v 是 V 中一点，求 v 到其它点的最短路径。

用 D(x,y) 表示 x,y 间最短路径长度，d(x,y) 表示 x,y 直连的长度。

设 X 是已经知道最短路径的点集，T 是与 X 相邻的点集，T' 是 X 中与 T 相邻的点集。

考虑 v=>t'->t 的路径长度，其中 t' in T', t in T,=> 表示最短路径:

设 (t',t) 是使得上述各路径中最短的点对，则  D(v, t)=D(v,t')+d(v',v)

从而 t 可以从 T 移动到 T' 中。

按上述方式反复操作，直到求出所有的 D(v, x), x in V。

[合理性]

设 (t',t) 入上所述，对任意从 v 到 t 的路径 p, 中间必定有 T’ 中的点，在路径中最右边的这样的点设为 t''，记路径 p’ 为 v=>t''-...->t，显然 p' 长度不超过 p。

(a) 若 t'' 和 t 直接相连，则由于  (t',t) 的定义，路径 v=>t'->t 不超过 v=>t''->t;

(b) 若 t'' 和 t 不是直接相连，设 p' 为 v=>t''->x->...->t。显然 x在 T 中。由于 (t',t) 的定义，路径 v=>t'->t 不超过 v=>t''->x，当然也不超过 v=>t''->x->...->t.


一般书上对 Dijkstra 的描述本质上跟这个是一样的，但更适合编程实现。

我这个的目标是容易理解－－－哎，好像还是很罗唆。