数据网络理论基础 第五章 路由算法

2024-05-30 12:04

本文主要是介绍数据网络理论基础 第五章 路由算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 图论基础*
    • 有限图和有向图
    • 关联, 相邻和邻接
    • 子图和生成子图
    • 端点的度
    • 图的运算
    • 路径与回路
    • 连通图
    • 哈密尔顿回路
    • 图的矩阵表示及特殊矩阵*
    • 割集
    • 平面图
  • 路由算法概论
    • 森林与树的概念*
    • 生成树的概念*
  • 最小生成树的概念**
    • 最小生成树的构造算法(Kruskal)***
    • 最小生成树的构造算法(Prim)***
  • 最短路
    • 基本概念
    • Dijkstra算法(标号法)***
    • Bellman-Ford算法(标号修正法)***
    • Floyd-Warshall算法***
  • 最大流算法****
    • 最大流最小割定理**
    • 最大流问题的标号法****
  • 距离矢量路由算法**

图论基础*

请添加图片描述

有限图和有向图

请添加图片描述

关联, 相邻和邻接

请添加图片描述

子图和生成子图

请添加图片描述

端点的度

请添加图片描述

请添加图片描述

请添加图片描述

图的运算

请添加图片描述

路径与回路

请添加图片描述

连通图

请添加图片描述

请添加图片描述

哈密尔顿回路

请添加图片描述

图的矩阵表示及特殊矩阵*

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

割集

请添加图片描述

平面图

请添加图片描述

路由算法概论

请添加图片描述

森林与树的概念*

请添加图片描述

请添加图片描述

生成树的概念*

请添加图片描述

最小生成树的概念**

请添加图片描述

请添加图片描述

最小生成树的构造算法(Kruskal)***

请添加图片描述
n是节点数量.

请添加图片描述

最小生成树的构造算法(Prim)***

请添加图片描述

v 1 v_1 v1开始, 列出S和S_补的割集, 找到割集中的最小边.

请添加图片描述

最短路

基本概念

请添加图片描述

请添加图片描述

Dijkstra算法(标号法)***

请添加图片描述

请添加图片描述

请添加图片描述

计算从 v 1 v_1 v1出发, 到各点的最小路. 一开始路径长度为 { 0 , ∞ , ∞ , ∞ , ∞ , ∞ } \{0,\infin,\infin,\infin,\infin,\infin\} {0,,,,,}

取出最小路径点, 更新标点集合 P P P, 依据该点更新路径长度, 直到 P P P满.

Bellman-Ford算法(标号修正法)***

请添加图片描述

  1. 从起点到其他各点;
  2. 允许有负权边, 不允许有负回路;

请添加图片描述

请添加图片描述

请添加图片描述

相比于迪杰斯特拉算法, BF算法属于是四个点一起更新.

Floyd-Warshall算法***

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述
请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

最大流算法****

请添加图片描述

请添加图片描述

请添加图片描述
可行流是一个全局的概念. 要求每条边上的流量不超过容量且流入流出之差满足特殊条件.

请添加图片描述

请添加图片描述

请添加图片描述

最大流最小割定理**

请添加图片描述

注意, 只有方向对的割集称为割集, 另一个是反向割集.

请添加图片描述

对于边 ( u , v ) (u,v) (u,v)和st方向相同, 是正向边, 反之为反向边. 对于正向边, 流小于流容量. 对于反向边, f ( v , u ) > 0 f(v,u)\gt0 f(v,u)>0. 顺着增广路走是可以增加流量的.
请添加图片描述

最大流问题的标号法****

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

距离矢量路由算法**

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

请添加图片描述

这篇关于数据网络理论基础 第五章 路由算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1016195

相关文章

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

SpringIntegration消息路由之Router的条件路由与过滤功能

《SpringIntegration消息路由之Router的条件路由与过滤功能》本文详细介绍了Router的基础概念、条件路由实现、基于消息头的路由、动态路由与路由表、消息过滤与选择性路由以及错误处理... 目录引言一、Router基础概念二、条件路由实现三、基于消息头的路由四、动态路由与路由表五、消息过滤

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时