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

 

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

 

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

 

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

 

 

看后更失望了,不够劲爆

 

 

 

 

 

 

 

 

 

 

 



推荐阅读
  • 计算机视觉领域介绍 | 自然语言驱动的跨模态行人重识别前沿技术综述(上篇)
    本文介绍了计算机视觉领域的最新进展,特别是自然语言驱动的跨模态行人重识别技术。上篇内容详细探讨了该领域的基础理论、关键技术及当前的研究热点,为读者提供了全面的概述。 ... [详细]
  • Squaretest:自动生成功能测试代码的高效插件
    本文将介绍一款名为Squaretest的高效插件,该工具能够自动生成功能测试代码。使用这款插件的主要原因是公司近期加强了代码质量的管控,对各项目进行了严格的单元测试评估。Squaretest不仅提高了测试代码的生成效率,还显著提升了代码的质量和可靠性。 ... [详细]
  • 尽管我们尽最大努力,任何软件开发过程中都难免会出现缺陷。为了更有效地提升对支持部门的协助与支撑,本文探讨了多种策略和最佳实践,旨在通过改进沟通、增强培训和支持流程来减少这些缺陷的影响,并提高整体服务质量和客户满意度。 ... [详细]
  • 在前文探讨了Spring如何为特定的bean选择合适的通知器后,本文将进一步深入分析Spring AOP框架中代理对象的生成机制。具体而言,我们将详细解析如何通过代理技术将通知器(Advisor)中包含的通知(Advice)应用到目标bean上,以实现切面编程的核心功能。 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 本文探讨了利用JavaScript实现集合的对称差集算法的方法。该算法旨在处理多个数组作为输入参数,同时保留每个数组中元素的原始顺序。算法不会移除单个数组内的重复元素,但会删除在不同数组之间出现的重复项。通过这种方式,能够有效地计算出多个数组的对称差集。 ... [详细]
  • 本文介绍了如何在iOS平台上使用GLSL着色器将YV12格式的视频帧数据转换为RGB格式,并展示了转换后的图像效果。通过详细的技术实现步骤和代码示例,读者可以轻松掌握这一过程,适用于需要进行视频处理的应用开发。 ... [详细]
  • 本文探讨了 Java 中 Pair 类的历史与现状。虽然 Java 标准库中没有内置的 Pair 类,但社区和第三方库提供了多种实现方式,如 Apache Commons 的 Pair 类和 JavaFX 的 javafx.util.Pair 类。这些实现为需要处理成对数据的开发者提供了便利。此外,文章还讨论了为何标准库未包含 Pair 类的原因,以及在现代 Java 开发中使用 Pair 类的最佳实践。 ... [详细]
  • AIX编程挑战赛:AIX正方形问题的算法解析与Java代码实现
    在昨晚的阅读中,我注意到了CSDN博主西部阿呆-小草屋发表的一篇文章《AIX程序设计大赛——AIX正方形问题》。该文详细阐述了AIX正方形问题的背景,并提供了一种基于Java语言的解决方案。本文将深入解析这一算法的核心思想,并展示具体的Java代码实现,旨在为参赛者和编程爱好者提供有价值的参考。 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • PHP网站日志深度解析与数据洞察分析
    通过对PHP网站日志进行深入解析与数据洞察分析,可以有效提升网站性能和用户体验。由于网站日志数据量庞大,通常需要借助专业的日志分析工具来处理。常用的工具包括光年日志分析工具和WebLog Expert等,这些工具能够帮助技术人员快速识别并解决网站运行中的各种问题,从而优化SEO效果和提升整体运营效率。 ... [详细]
  • 在Android 4.4系统中,通过使用 `Intent` 对象并设置动作 `ACTION_GET_CONTENT` 或 `ACTION_OPEN_DOCUMENT`,可以从相册中选择图片并获取其路径。具体实现时,需要为 `Intent` 添加相应的类别,并处理返回的 Uri 以提取图片的文件路径。此方法适用于需要从用户相册中选择图片的应用场景,能够确保兼容性和用户体验。 ... [详细]
  • 本文介绍了 Vue 开发的入门指南,重点讲解了开发环境的配置与项目的基本搭建。推荐使用 WebStorm 作为 IDE,其下载地址为 。安装时请选择适合您操作系统的版本,并通过 获取激活码。WebStorm 是前端开发者的理想选择,提供了丰富的功能和强大的代码编辑能力。 ... [详细]
  • ButterKnife 是一款用于 Android 开发的注解库,主要用于简化视图和事件绑定。本文详细介绍了 ButterKnife 的基础用法,包括如何通过注解实现字段和方法的绑定,以及在实际项目中的应用示例。此外,文章还提到了截至 2016 年 4 月 29 日,ButterKnife 的最新版本为 8.0.1,为开发者提供了最新的功能和性能优化。 ... [详细]
  • 本文探讨了资源访问的学习路径与方法,旨在帮助学习者更高效地获取和利用各类资源。通过分析不同资源的特点和应用场景,提出了多种实用的学习策略和技术手段,为学习者提供了系统的指导和建议。 ... [详细]
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社区 版权所有