【数据结构(邓俊辉)学习笔记】图07——最短路径

2024-06-10 11:28

本文主要是介绍【数据结构(邓俊辉)学习笔记】图07——最短路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 0. 概述
  • 1. 问题
  • 2. 最短路径
    • 2.1 最短路径树
      • 2.1.1 单调性
      • 2.1.2 歧义性
      • 2.1. 3 无环性
    • 2.2 Dijkstra 算法
      • 2.2.1 贪心迭代
      • 2.2.2 实现
      • 2.2.3 实例
      • 2.2.4 复杂度

0. 概述

学习下最短路径和Dijistra算法

1. 问题

在这里插入图片描述
给定带权网络G = (V, E),以及源点(source)s ∈ V,对于所有的其它顶点v,s到v的最短通路有多长?该通路由哪些边构成?

2. 最短路径

2.1 最短路径树

2.1.1 单调性

在这里插入图片描述
设顶点s到v的最短路径为 ρ \rho ρ。于是对于该路径上的任一顶点u,若其在 ρ \rho ρ上对应的前缀为 σ \sigma σ,则 σ \sigma σ也必
是s到u的最短路径(之一)。

2.1.2 歧义性

较之最小支撑树,最短路径的歧义性更难处理。首先,即便各边权重互异,从s到v的最短路径也未必唯一。另外,当存在非正权重的边,并导致某个环路的总权值非正时,最短路径甚至无从定义。因此以下不妨假定,带权网络G内各边权重均大于零。

2.1. 3 无环性

在这里插入图片描述考查从源点到其余顶点的最短路径(若有多条,任选其一)。于是由以上单调性,这些路径的并集必然不含任何(有向)回路。这就意味着,如图所示,构成所谓的最短路径树(shortest-path tree)。

2.2 Dijkstra 算法

2.2.1 贪心迭代

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

上述思路可知,只要能够确定 u k + 1 u_{k+1} uk+1,便可反过来将 T k T_k Tk扩展为 T k + 1 T_{k+1} Tk+1。如此,便可按照到s距离的非降次序,逐一确定各个顶点{ u 1 u_1 u1, u 2 u_2 u2, …, u n u_n un},同时得到各棵最短路径子树,并得到最终的最短路径树T = T n T_n Tn。现在,问题的关键就在于:
~~~~~~~~~~~~~~~~~~                   如何才能高效地找到 u k + 1 u_{k+1} uk+1
实际上,由最短路径子树序列的上述性质,每一个顶点 u k + 1 u_{k+1} uk+1都是在 T k T_k Tk之外,距离s最近者。若将此距离作为各顶点的优先级数,则与最小支撑树的Prim算法类似,每次将 u k + 1 u_{k+1} uk+1加入 T k T_k Tk并将其拓展至 T k + 1 T_{k+1} Tk+1后,需要且只需要更新那些仍在 T k + 1 T_{k+1} Tk+1之外,且与 T k + 1 T_{k+1} Tk+1关联的顶点的优先级数。

可见,该算法与Prim算法仅有一处差异:考虑的是 u k + 1 u_{k+1} uk+1到s的距离,而不再是其到 T k T_k Tk的距离。

2.2.2 实现

与Prim算法一样,Dijkstra算法也可纳入此前的优先级搜索算法框架。

在这里插入图片描述

为此,每次由 T k T_k Tk扩展至 T k + 1 T_{k+1} Tk+1时,可将 V k V_k Vk之外各顶点u到 V k V_k Vk的距离看作u的优先级数(若u与 V k V_k Vk内顶点均无联边,则优先级数设为+∞)。如此,每一最短跨越边 e k e_k ek所对应的顶点 u k u_k uk,都会因拥有最小的优先级数(或等价地,最高的优先级)而被选中。

在这里插入图片描述
唯一需要专门处理的是,在 u k u_k uk e k e_k ek加入 T k T_k Tk之后,应如何快速地更新 V k + 1 V_{k+1} Vk+1以外顶点的优先级数。实际上,只有与 u k u_k uk邻接的那些顶点,才有可能在此后降低优先级数。因此与Prim算法一样,也可遍历 u k u_k uk的每一个邻居v,只要边 u k v u_kv ukv的权重加上 u k u_k uk的优先级数,小于v当前的优先级数,即可将后者更新为前者。

2.2.3 实例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2.2.4 复杂度

不难看出,以上顶点优先级更新器只需常数运行时间。同样根据对PFS搜索性能的分析结论,Dijkstra算法这一实现版本的时间复杂度为O( n 2 n^2 n2)。

作为PFS搜索的特例,Dijkstra算法的效率也可借助优先级队列进一步提高。

这篇关于【数据结构(邓俊辉)学习笔记】图07——最短路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学