热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

最短路径_OSPF中的最短路径算法:Dijkstra算法

篇首语:本文由编程笔记#小编为大家整理,主要介绍了OSPF中的最短路径算法:Dijkstra算法相关的知识,希望对你有一定的参考价值。

篇首语:本文由编程笔记#小编为大家整理,主要介绍了OSPF 中的最短路径算法:Dijkstra 算法相关的知识,希望对你有一定的参考价值。


OSPF 中的最短路径算法:Dijkstra 算法

 

前言

OSPFOpen Shortest Path First,开放最短路径优先)是IETFInternet Engineering Task Force,互联网工程任务组)组织开发的一个基于链路状态的内部网关协议。目前针对IPv4协议使用的是OSPF Version 2

OSPF 所使用的最短路径算法就是 Dijkstra 算法。该算法取名于作者本人。艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra1930511~200286日)荷兰人。 计算机科学家,毕业就职于荷兰Leiden大学,早年钻研物理及数学,而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖,之后,他还获得过1974AFIPS Harry Goode Memorial Award1989ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002ACM PODC最具影响力论文奖。(摘自百度百科)

 

 

OSPF 中的最短路径算法:Dijkstra 算法


 

1959年,Dijkstra 提出了 Dijkstra 算法。由于 OSPF,很多人都了解和熟悉该算法,网上也有很多文章介绍该算法。本文班门弄斧,希望能做到有所不一样——更加清晰易懂。

 

一、Dijkstra 算法的问题模型和目标

Dijkstra 算法是很经典的求解“单源最短路径” 问题的算法。“单源最短路径” 问题指的是:已知一个由n个节点(V0..n)构成的有向连通图G=(VE),以及图中边的权函数C (E),其中V代表节点集合,E表示所有边的集合,并假设所有权非负,求由G中指定节点V0到其他各个节点的最短路径。


我不知道有多少人看到上述介绍以后,就默默地关掉网页(书本),然后忧郁地点上一根烟......何必要跟自己过不去......

 

要研究算法,严谨的数学抽象和数学术语,是必须的,而且是研究的第一步。所幸呢,吾辈还谈不上研究,只是学习而已。既然仅仅是为了学习,那就尽量少点术语,多点白话吧。

如图1所示:

 

 

OSPF 中的最短路径算法:Dijkstra 算法

图1:Dijkstra 问题模型示意图

 

1Dijkstra 问题模型的一个简化示意图,它不够全面,但是足够说明问题。

 

1、模型简述

1中,有 N 个点(A/B/C/D/E/F),两点之间有直连线路(比如 A-B 之间),也可能没有(比如 A-C 之间)。

线路是有方向的,比如 A B 是通的,而 B A 是不通的(图1中的线路方向是 A B)。

线路是长度的,比如 A-B 的长度是15A-D 的长度是10。非常重要的一点,所有线路的长度都是正数。这一点非常非常非常重要!

 

2、算法目标

Dijkstra 算法的目标,是计算图中其中一个点,分别到其余所有点之间的最短路径。比如图1中的 A 点,到B点的最短路径是什么,到 C 点的最短路径是什么......F 点的最短路径是什么。

它不会去计算、也不需要计算其它各点之间的最短路径,比如不需要计算 B-C 之间的最短路径是什么。

这里的最短路径,指的是长度最短的路径,并且要说明这个路径经过了哪些节点。比如 A-C 之间的最短路径长度是15,经过了 A-D-C 三个节点。

 

二、路径标识

路径标识,是算法的第一步。如图2所示:

 

 

OSPF 中的最短路径算法:Dijkstra 算法

图2:路径标识示意图

 

任意两点之间,有的是有直连线路,那么这个路径标识就不变,仍然是那个直连线路,并且路径长度也是原来的长度。

如果两点之间没有直连线路,那么就以红色虚线标识,并且其长度记为(无穷大)。

需要说明两点:

1)所谓红色虚线,是给人看的。具体在计算机编程中,如何标识,仁者见仁,智者见智。

2)图2中,并没有标识完备。严格地说,以 A-B 为例,还需要标识一个 B 到 A 的红色虚线,并且设置其长度为∞。图中只是为了看起来更清晰一些,而没有画出来而已。(图中也没有画出 C 到 F 之间的红色虚线...)

 

三、算法介绍

标识完路径以后,就可以进入最短路径的计算了。再强调一遍,Dijkstra 算法只是为了计算其中一个点到其余各点的最短路径。

 

1、路径表的初始构建

为什么再次强调算法的目标?这是因为我们要构建路径表。 Dijkstra 算法的目标很简单,所以这个路径表也非常简单直接,如表1所示:

 

1Dijkstra 算法的路径表





























路径名称

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所示:

 

 

OSPF 中的最短路径算法:Dijkstra 算法

图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 本人早就证明这个算法是正确的了。

 

重要的是,这篇文章,是否与其他文章不一样,是否足够的清晰易懂,是否对您有所帮助。

 

我试图换一种文风来写这类文章,比如搞笑型......唉,没想出来该如何写。

 

有很多童鞋说,看我的文章,不是来看字的,是来看图的。今天太晚了,就没有去网上搜索图片,最后补上一张吧。既然您都看到最后了,总不能让您失望而归!

 

 

看后更失望了,不够劲爆

 

 

 

 

 

 

 

 

 

 

 



推荐阅读
  • C/C++ 应用程序的安装与卸载解决方案
    本文介绍了如何使用Inno Setup来创建C/C++应用程序的安装程序,包括自动检测并安装所需的运行库,确保应用能够顺利安装和卸载。 ... [详细]
  • 笔记说明重学前端是程劭非(winter)【前手机淘宝前端负责人】在极客时间开的一个专栏,每天10分钟,重构你的前端知识体系& ... [详细]
  • Python环境下OpenCV的安装与验证方法
    本文介绍了如何在Python环境中安装OpenCV库及其额外模块,并提供了验证安装是否成功的具体步骤和代码示例。 ... [详细]
  • Excel技巧:单元格中显示公式而非结果的解决方法
    本文探讨了在Excel中如何通过简单的方法解决单元格显示公式而非计算结果的问题,包括使用快捷键和调整单元格格式两种方法。 ... [详细]
  • 本文详细探讨了如何根据不同的应用场景选择合适的PHP版本,包括多版本切换技巧、稳定性分析及针对WordPress等特定平台的版本建议。 ... [详细]
  • 本文探讨了如何使用Scrapy框架构建高效的数据采集系统,以及如何通过异步处理技术提升数据存储的效率。同时,文章还介绍了针对不同网站采用的不同采集策略。 ... [详细]
  • Gradle 是 Android Studio 中默认的构建工具,了解其基本配置对于开发效率的提升至关重要。本文将详细介绍如何在 Gradle 中定义和使用共享变量,以确保项目的一致性和可维护性。 ... [详细]
  • 汇总了2023年7月7日最新的网络安全新闻和技术更新,包括最新的漏洞披露、工具发布及安全事件。 ... [详细]
  • Canopy环境安装与使用指南
    《利用Python进行数据分析》一书推荐使用EPDFree版本的环境,然而随着技术的发展,目前更多人倾向于使用Canopy。本文将详细介绍Canopy的安装及使用方法。 ... [详细]
  • 本文分享了作者在使用LaTeX过程中的几点心得,涵盖了从文档编辑、代码高亮、图形绘制到3D模型展示等多个方面的内容。适合希望深入了解LaTeX高级功能的用户。 ... [详细]
  • 本文详细介绍如何在SSM(Spring + Spring MVC + MyBatis)框架中实现分页功能。包括分页的基本概念、数据准备、前端分页栏的设计与实现、后端分页逻辑的编写以及最终的测试步骤。 ... [详细]
  • Go语言实现文件读取与终端输出
    本文介绍如何使用Go语言编写程序,通过命令行参数指定文件路径,读取文件内容并将其输出到控制台。代码示例中包含了错误处理和资源管理的最佳实践。 ... [详细]
  • 本文介绍了如何在C# WinForms应用程序中通过自定义绘制实现圆形按钮的方法,适合初学者参考。 ... [详细]
  • 本文详细介绍了 Node.js 中 OS 模块的 arch 方法,包括其功能、语法、参数以及返回值,并提供了具体的使用示例。 ... [详细]
  • 本文基于Java官方文档进行了适当修改,旨在介绍如何实现一个能够同时处理多个客户端请求的服务端程序。在前文中,我们探讨了单客户端访问的服务端实现,而本篇将深入讲解多客户端环境下的服务端设计与实现。 ... [详细]
author-avatar
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有