篇首语:本文由编程笔记#小编为大家整理,主要介绍了OSPF 中的最短路径算法:Dijkstra 算法相关的知识,希望对你有一定的参考价值。
OSPF 中的最短路径算法:Dijkstra 算法
【前言】
OSPF(Open Shortest Path First,开放最短路径优先)是IETF(Internet Engineering Task Force,互联网工程任务组)组织开发的一个基于链路状态的内部网关协议。目前针对IPv4协议使用的是OSPF Version 2。
OSPF 所使用的最短路径算法就是 Dijkstra 算法。该算法取名于作者本人。艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra,1930年5月11日~2002年8月6日)荷兰人。 计算机科学家,毕业就职于荷兰Leiden大学,早年钻研物理及数学,而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖,之后,他还获得过1974年 AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。(摘自百度百科)
1959年,Dijkstra 提出了 Dijkstra 算法。由于 OSPF,很多人都了解和熟悉该算法,网上也有很多文章介绍该算法。本文班门弄斧,希望能做到有所不一样——更加清晰易懂。
一、Dijkstra 算法的问题模型和目标
Dijkstra 算法是很经典的求解“单源最短路径” 问题的算法。“单源最短路径” 问题指的是:已知一个由n个节点(V0..n)构成的有向连通图G=(V,E),以及图中边的权函数C (E),其中V代表节点集合,E表示所有边的集合,并假设所有权非负,求由G中指定节点V0到其他各个节点的最短路径。
我不知道有多少人看到上述介绍以后,就默默地关掉网页(书本),然后忧郁地点上一根烟......何必要跟自己过不去......
要研究算法,严谨的数学抽象和数学术语,是必须的,而且是研究的第一步。所幸呢,吾辈还谈不上研究,只是学习而已。既然仅仅是为了学习,那就尽量少点术语,多点白话吧。
如图1所示:
图1:Dijkstra 问题模型示意图
图1是 Dijkstra 问题模型的一个简化示意图,它不够全面,但是足够说明问题。
1、模型简述
图1中,有 N 个点(A/B/C/D/E/F),两点之间有直连线路(比如 A-B 之间),也可能没有(比如 A-C 之间)。
线路是有方向的,比如 A 到 B 是通的,而 B 到 A 是不通的(图1中的线路方向是 A 到 B)。
线路是长度的,比如 A-B 的长度是15,A-D 的长度是10。非常重要的一点,所有线路的长度都是正数。这一点非常非常非常重要!
2、算法目标
Dijkstra 算法的目标,是计算图中其中一个点,分别到其余所有点之间的最短路径。比如图1中的 A 点,到B点的最短路径是什么,到 C 点的最短路径是什么......到 F 点的最短路径是什么。
它不会去计算、也不需要计算其它各点之间的最短路径,比如不需要计算 B-C 之间的最短路径是什么。
这里的最短路径,指的是长度最短的路径,并且要说明这个路径经过了哪些节点。比如 A-C 之间的最短路径长度是15,经过了 A-D-C 三个节点。
二、路径标识
路径标识,是算法的第一步。如图2所示:
图2:路径标识示意图
任意两点之间,有的是有直连线路,那么这个路径标识就不变,仍然是那个直连线路,并且路径长度也是原来的长度。
如果两点之间没有直连线路,那么就以红色虚线标识,并且其长度记为∞(无穷大)。
需要说明两点:
(1)所谓红色虚线,是给人看的。具体在计算机编程中,如何标识,仁者见仁,智者见智。
(2)图2中,并没有标识完备。严格地说,以 A-B 为例,还需要标识一个 B 到 A 的红色虚线,并且设置其长度为∞。图中只是为了看起来更清晰一些,而没有画出来而已。(图中也没有画出 C 到 F 之间的红色虚线...)
三、算法介绍
标识完路径以后,就可以进入最短路径的计算了。再强调一遍,Dijkstra 算法只是为了计算其中一个点到其余各点的最短路径。
1、路径表的初始构建
为什么再次强调算法的目标?这是因为我们要构建路径表。 Dijkstra 算法的目标很简单,所以这个路径表也非常简单直接,如表1所示:
表1:Dijkstra 算法的路径表
路径名称 |
A到B (D0) |
A到C (D1) |
A到D (D2) |
A到E (D3) |
A到F (D4) |
路径距离 |
18 |
∞ |
10 |
∞ |
15 |
路径节点 |
A-B |
NULL |
A-D |
NULL |
A-F |
Dijkstra 算法路径表,就是构建其中一个节点(A)到其余各节点之间的路径。初始构建方法是:
(1)两点之间如果有直连线路,则其路径长度就是直连线路的长度,比如“A到B”路径;
(2)如果没有,则路径距离记为∞,路径节点记为 NULL,比如“A到C”路径。
2、最短路径判断
这一步非常重要!非常重要!非常重要!也非常关键!非常关键!非常关键!
懂得这一步,就相当于拿到了 Dijkstra 算法的钥匙!
根据路径表,我们现在有5个路径距离,分别记作:D0、D1...D5。
在这5个(或者抽象地说,是 N 个)路径距离中,最短的那个距离,就是相应路径的最短路径。
这么说有点拗口,直接看路径表,如表1所示,5个距离中,最短距离是 D2(等于10),那么,A到D的最短路径就是10,其所经过的节点就是 A-D。
为了能看懂这个算法,其实您可以自己想一下为什么,而不用看我下面的证明,这样的话,可能比看下面的证明更容易理解。不过我还是证明一下。
证明:(反证法)
假设“A到D”的最短路径不是“A-D”,而是“A-X-D”,其中 X 为 B/C/E/F中任意一点,那么:
(1)A-D 路径的长度为:10
(2)A-X-D 路径的长度为:A-X 的长度 + X-D 的长度。
因为,A-X 的长度已经大于 A-D 的长度(前面已经说过,A-D 的长度,是 A 到所有节点中的最短长度),所以 A-X-D 的长度,肯定大于 A-D 的长度(因为前面说过,所有路径的长度,都是正数)。
所以,原假设不成立,也就是说 A到D之间的最短路径就是 A-D(长度为10)。
其实,上述的证明表述,不是很严格,严格的说,应该将 A-X-D 换为 A-X1-...Xn-D。不过这只是数学上严格表述的问题,对于理解问题的本质来说,A-X-D 的表述是一样的,而且更简洁。
我努力将这个证明写得很容易理解,但是,仍然需要您仔细阅读。走马观花、浮光掠影,可能看不懂(虽然证明本身很简单)。
3、最短路径标色
既然上一步已经得到了一个最短路径(A到D的路径:A-D),那么我们就将这个最短路径标一个颜色,以表明我们前进了一小步,如表2所示:
表2:最短路径标色
路径名称 |
A到B (D0) |
A到C (D1) |
A到D (D2) |
A到E (D3) |
A到F (D4) |
路径距离 |
18 |
∞ |
10 |
∞ |
15 |
路径节点 |
A-B |
NULL |
A-D |
NULL |
A-F |
当然,还是那句话,所谓的标色,是为了给人看的,具体到计算机编程,采用什么方法进行“标色”,仁者见仁,智者见智。
4、迭代路径表
计算出了一条最短路径,并且也标了颜色,下一步做什么呢?
这很关键,时间关系,我不再给出证明,而是直接给出算法中,下一步做什么:迭代路径表。
所谓迭代路径表,就是以上一个最短路径(A-D)为基础,再重新计算一遍路径,如图3所示:
图3:基于 A-D 再重新计算路径
图3中,基于 A-D,可以计算出 A到C 的路径是 A-D-C,长度是16,比原来的路径 A-C(长度是 ∞)长度要短,所以 A到C的路径就从A-C替换为A-D-C。
同理,A到E的路径,替换为 A-D-E,长度为18。
不仅 A到C,A到E的路径要重新计算,A到B、A到F的路径也要重新计算,只不过计算的结果大于原来的路径长度,不作替换而已。
比如,A到B的路径,如果基于A-D的话,则是A-D-B,由于 D-B 的长度是∞,所以 A-D-B 的长度也是∞,比原来的A-B路径(距离是18)要长,所以,不作替换。
如此一来,基于 A-D 再重新计算路径后,所得的路径表,如表3所示:
表3:重新计算后的路径表
路径名称 |
A到B (D0) |
A到C (D1) |
A到D (D2) |
A到E (D3) |
A到F (D4) |
路径距离 |
18 |
16 |
10 |
18 |
15 |
路径节点 |
A-B |
A-D-C |
A-D |
A-D-E |
A-F |
5、再获取最短路径
在步骤2中,我们已经得到一个最短路径,就是A到D的最短路径A-D。现在我们可以基于重新计算后的路径表,再获取一个最短路径。
在表3中,已经标识为最短路径(绿色)的A到D的路径,不参与计算,而其余的路径,计算出一个最小值,也就是 A到F的路径“A-F”,其长度为15。
根据步骤2中的证明,可以知道,这条路径,就是A到F的最短路径。所以,我们将这条路径也进行标色,如表4所示:
表4:继续标色最短路径
路径名称 |
A到B (D0) |
A到C (D1) |
A到D (D2) |
A到E (D3) |
A到F (D4) |
路径距离 |
18 |
16 |
10 |
18 |
15 |
路径节点 |
A-B |
A-D-C |
A-D |
A-D-E |
A-F |
6、循环迭代,直至结束
根据上面的描述,我们已经知道该如何循环迭代了,直至结束:所有的最短路径都计算出来。如表5所示:
表5:所有的最短路径
路径名称 |
A到B (D0) |
A到C (D1) |
A到D (D2) |
A到E (D3) |
A到F (D4) |
路径距离 |
18 |
16 |
10 |
18 |
15 |
路径节点 |
A-B |
A-D-C |
A-D |
A-D-E |
A-F |
所有的最短路径,用图来表示,如图4所示:
图4:所有的最短路径
【结束语】
时间关系,本文没有给出迭代算法所得出的结果,就是正确的结果,以后有时间再补上吧。
可能是否补充这个证明也不是多么重要,毕竟 Dijkstra 本人早就证明这个算法是正确的了。
重要的是,这篇文章,是否与其他文章不一样,是否足够的清晰易懂,是否对您有所帮助。
我试图换一种文风来写这类文章,比如搞笑型......唉,没想出来该如何写。
有很多童鞋说,看我的文章,不是来看字的,是来看图的。今天太晚了,就没有去网上搜索图片,最后补上一张吧。既然您都看到最后了,总不能让您失望而归!
看后更失望了,不够劲爆