互联网IP路由的逐跳全局最优化原则-Dijkstra算法证明

把周末写了一半的东西继续补齐了,实现了完美的一天。
逐跳全局最优化IP路由是在每一台路由器上逐跳路由的,那么就产生了一个问题,偌大一个互联网,该怎么相信这么多逐跳路由拼接起来的一条完整的路径确实是最优化的呢?答案显然是确定的,问题是怎么证明它。
路由算法书上讲,路由算法基本分为距离矢量算法和链路状态算法,各自的协议代表作就是RIP和OSPF(我就是靠着这两个找到的第一份工作),确实是这样,但是从这些算法的正确性的证明过程中,你就会发现,确实是“逐跳的最优化路由真的就是全局的最优化路由”。本文中我仅仅给出基于链路状态路由协议的Dijkstra算法的证明,因为全网每台设备的链路状态数据库都是相同的,所以它是很好理解的。
Dijkstra算法正确性证明首先要给出Dijkstra算法正确性的证明,才能进行后续的。毕竟,Dijkstra算法本身只是指导了step by step的操作步骤,并没没能证明这么折腾一圈得到的最短路径树中的每一条路径确实是最短的。而要想证明逐跳全局最优化原则,需要这个事实。

互联网IP路由的逐跳全局最优化原则-Dijkstra算法证明

逐跳全局最优化的问题

下面的示意图点名了逐跳全局最优化的问题所在:

互联网IP路由的逐跳全局最优化原则-Dijkstra算法证明

逐跳全局最优化的证明

下面的示意图给出了逐跳全局最优化的简单证明,证明方式多种多样,我这里给出的仅仅是其中一种:

互联网IP路由的逐跳全局最优化原则-Dijkstra算法证明
渗透的痕迹,就会理解Dijkstra算法,它确实是不证自明的。大自然是懒惰的,总是用最省力的方式行事,水分子在落地那个点开始,在崎岖不平的地上由于重力(暂时不考虑其它分子力)沿着一定的路径到达一系列点,这些路径一定是最短路径。我们可以把地面的崎岖程度视为路径的权值,这不就和Dijkstra算法模型一模一样吗?

分类:默认分类 时间:2012-01-06 人气:7
本文关键词:
分享到:

相关文章

  • hdu 1690 Bus System 最短路(Dijkstra算法) 2012-06-14

    Bus System Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Because of the huge population of China, public transportation is very important. Bus is an important transportation method in traditional

  • hdu 4725 The Shortest Path in Nya Graph(dijkstra+优先队列) 2012-08-18

    题目链接:hdu 4725 The Shortest Path in Nya Graph 题目大意:n个点,m条边,以及相邻层之间移动的代价c,给出每个点所在的层数,以及m条边,每条边有u,v,val,表示从节点u到v(无向),并且移动的代价val,问说从1到n的代价最小是多少。 解题思路:dijkstra算法,主要是建图,每一层有一个汇点,汇点连接所有处于当前层的点,代价为0,相邻层之间如果两层都有点的话,连接,代价为c,然后每个点连接上下层的汇点,代价c(这里我一开始写将当前点连接到当前层的

  • Dijkstra.Bellman_Ford.SPFA.Floyd算法复杂度比较 2012-10-08

    Dijkstra:适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV) BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE) SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处的复杂度证明是有问题的,其实SPFA的最坏情况应该是O(VE). Floyd:每对节点之间的最短路径。 先给出结论: (1)当权值为非负时,用Dijkstra。 (

  • 经典算法研究系列:二.Dijkstra 算法初探 2012-11-23

    July 二零一一年一月 ====================== 本文主要参考:算法导论 第二版、维基百科。 写的不好之处,还望见谅。 本经典算法研究系列文章,永久勘误,永久更新、永久维护。 July、二零一一年二月十日更新。 一、Dijkstra 算法的介绍 Dijkstra 算法,又叫迪科斯彻算法(Dijkstra), 算法解决的是有向图中单个源点到其他顶点的最短路径问题。 举例来说, 如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离, Dijkstra 算法可以用来找到

  • Dijkstra算法求最短路径(java) 2013-01-03

    Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式 用OPEN,CLOSE表的方式,其采用的是贪心法的算法策略,大概过程如下: 1.声明两个集合,open和close,open用于存储未遍历的节点,close用来存储已遍历的节点 2.初始阶段,将初始节点放入close,其他所有节点放

  • HDU 1874-畅通工程续(Dijkstra+优先队列) 2013-01-05

    畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 28578 Accepted Submission(s): 10382 Problem Description 某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短

  • HDU 2112 HDU Today (Dijkstra算法) 2013-05-04

    HDU Today Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 13952 Accepted Submission(s): 3264 Problem Description 经过锦囊相助,海东集团终于度过了危机,从此,HDU的发展就一直顺风顺水,到了2050年,集团已经相当规模了,据说进入了钱江肉丝经济开发区500强。这时候,XHD夫妇

  • POJ 3268-Silver Cow Party(dijkstra算法) 2013-05-10

    题目大意:给出一个单向带权图和一个点s,求点u,u到s的最短路径和s到u的最短路径之和最大。 对于s到任意点的最短路,直接dijkstra可以求出。 对于任意点到s的最短路,如果将所有边反向然后求一次最短路,容易证明,求出的s到任意点v的最短路s-->v就是原来没有反向的图的v-->s的最短路。 所以先求一次dijkstra,保存此次的结果,然后把所有的边反向,权值不变,再求一次dijkstra,将两次结果加起来,计算它们之中的最大值。 #include #include #incl

  • HDU 1535 Invitation Cards 2次Dijkstra 2013-05-12

    题意:从1派学生到2-n这n-1个点 求去并且回来的最短路 就是1到各点的最短路之和和各点到1的最短路之和 给的是有向图 思路:对于1到各个点的最短路直接Dijkstra求出无压力 然后各个点到1的最短路可以反向建图后再求一次从1到各个点的最短路 对于很多点到一个点的情况可以考虑反向建图 转变成单源最短路 #include #include #include #include using namespace std; const int maxn = 1000010; struct edge {

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.136 (s). 10 q(s)