Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1105660
  • 博文数量: 25
  • 博客积分: 10535
  • 博客等级: 上将
  • 技术积分: 2746
  • 用 户 组: 普通用户
  • 注册时间: 2004-11-21 23:21
文章分类

全部博文(25)

文章存档

2011年(1)

2010年(3)

2009年(2)

2008年(19)

分类:

2008-05-25 22:32:01

最近要给人讲路由,其中的 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 的描述本质上跟这个是一样的,但更适合编程实现。

我这个的目标是容易理解---哎,好像还是很罗唆。
阅读(1690) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~