【Algorithms 4】算法(第4版)学习笔记 18 - 4.4 最短路径

文章目录

    • 前言
    • 参考目录
    • 学习笔记
      • 0:引入介绍
      • 1:APIs
      • 1.1:API:加权有向边
      • 1.2:Java 实现:加权有向边
      • 1.3:API:加权有向图
      • 1.4:Java 实现:加权有向图
      • 1.5:API:最短路径
      • 2:最短路径性质
      • 2.1:最短路径的数据结构
      • 2.2:边的松弛 edge relaxation
      • 2.3:最优性条件 optimality conditions
      • 2.4:通用算法 generic shortest-paths algorithm
      • 3:Dijkstra 算法
      • 3.1:demo 演示
      • 3.2:证明
      • 3.3:Java 实现
      • 3.4:计算图生成树
      • 3.5:运行时间
      • 4:无环加权有向图 edge-weighted DAGs
      • 4.1:demo 演示
      • 4.2:证明
      • 4.3:Java 实现
      • 4.4:最长路径
      • 5:负权重 negative weights
      • 5.1:失败尝试
      • 5.2:负权重环 negative cycles
      • 5.3:Bellman-Ford 算法
      • 5.3.1:demo 演示
      • 5.3.2:算法分析
      • 5.4:成本开销小结
      • 6:小结

前言

本篇主要内容包括:APIs最短路径性质Dijkstra 算法无环加权有向图 以及 负权重

参考目录

  • B站 普林斯顿大学《Algorithms》视频课
    (请自行搜索。主要以该视频课顺序来进行笔记整理,课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。)
  • 微信读书《算法(第4版)》
    (本文主要内容来自《4.4 最短路径》)
  • 官方网站
    (有书本配套的内容以及代码)

学习笔记

注1:下面引用内容如无注明出处,均是书中摘录。
注2:所有 demo 演示均为视频 PPT demo 截图。
注3:如果 PPT 截图中没有翻译,会在下面进行汉化翻译,因为内容比较多,本文不再一一说明。

0:引入介绍

加权有向图的最短路径(shortest paths in an edge-weighted digraph):

![image-20240315082159395]

最短路径的应用:

![L15-44ShortestPaths_03]在这里插入图片描述

  • PERT/CPM:计划评审技术/关键路径法
  • 地图路线规划
  • 接缝雕刻(图像缩放中的内容感知算法)
  • 纹理映射(计算机图形学中将图像纹理贴到三维模型表面的技术)
  • 机器人导航技术
  • TeX 中的排版设置
  • 城市交通规划
  • VLSI 芯片的最佳流水线设计
  • 电话营销员操作员调度问题
  • 电信消息的路由选择
  • 网络路由协议(如 OSPF、BGP、RIP)
  • 利用货币兑换市场中的套利机会
  • 根据既定交通拥堵模式确定卡车最优行驶路线

Shortest path is a really interesting and important problem solving model. There’s all kinds of important practical problems that can be recast as shortest paths problems. And because we have efficient solutions to the shortest path, efficient algorithms for finding shortest paths, we have efficient solutions to all these kinds of problems.

最短路径是一个非常有趣且重要的问题解决模型。许多重要的实际问题都可以被重新表述为最短路径问题。正因为如此,我们拥有寻找最短路径的有效解决方案,即高效的最短路径算法,因此也就拥有了解决这类各种问题的有效方法。

最短路径的不同类型:

![L15-44ShortestPaths_04]

顶点类型:

  • 单源:从一个顶点 s 到其他所有顶点。
  • 单汇点:从每个顶点到另一个特定顶点 t。
  • 源汇点:从一个顶点 s 到另一个顶点 t。
  • 全对全:在所有顶点对之间。

边权重限制:

  • 非负权重:所有边的权重都是非负数。
  • 欧几里得权重:边权重基于欧几里得距离。
  • 任意权重:边的权重可以是任意数值。

循环条件:

  • 无有向循环:图中不存在有向循环。
  • 无负权循环:图中不存在权重总和为负值的循环。

简化假设: 从顶点 s 到每个顶点 v 都存在最短路径。

1:APIs

1.1:API:加权有向边

![image-20240315085348075]

1.2:Java 实现:加权有向边

edu.princeton.cs.algs4.DirectedEdge

![image-20240315085631710]

![image-20240315085644190]

1.3:API:加权有向图

![image-20240315085915603]

![image-20240315090301981]

![image-20240315090431816]

1.4:Java 实现:加权有向图

edu.princeton.cs.algs4.EdgeWeightedDigraph

![image-20240315092205110]

![image-20240315092241700]

1.5:API:最短路径

![image-20240315092512628]

2:最短路径性质

2.1:最短路径的数据结构

![L15-44ShortestPaths_14]

目标: 找到从顶点 s 到其他所有顶点的最短路径。

观察结论: 存在一种最短路径树(Shortest Paths Tree, SPT)解法。为什么?

结果: 可以通过两个以顶点索引为键的数组来表示 SPT:

  • distTo[v] 表示从顶点 s 到顶点 v 的最短路径长度。
  • edgeTo[v] 表示从顶点 s 到顶点 v 的最短路径上的最后一段边。

![image-20240315094302501]

对应书本的介绍:

![image-20240315093903240]

2.2:边的松弛 edge relaxation

![L15-44ShortestPaths_16]

对边 e = v → w 进行松弛操作时:

  • distTo[v] 保存已知从源点 s 到顶点 v 的最短路径长度。
  • distTo[w] 保存已知从源点 s 到顶点 w 的最短路径长度。
  • edgeTo[w] 记录已知从源点 s 到顶点 w 的最短路径上最后经过的边。
  • 若通过边 e = v → w 能够到达顶点 w,并且这条路径比之前已知的从 s 到 w 的最短路径更短,则更新 distTo[w] 以及 edgeTo[w]

![image-20240315095849401]

2.3:最优性条件 optimality conditions

![image-20240315100606867]

命题: 设G是一个带权有向图(edge-weighted digraph),则 distTo[] 数组存储的是从源点 s 到各顶点的最短路径距离,当且仅当满足以下条件:

  • distTo[s] = 0,即源点s到自身的最短路径距离为0。
  • 对于每个顶点 v,distTo[v] 表示从源点 s 到顶点 v 的某条路径的长度。
  • 对于每条边 e = v → wdistTo[w] 的值小于等于从源点 s 经由顶点 v 再到顶点 w 的路径长度,即 distTo[w] ≤ distTo[v] + e.weight(),其中 e.weight() 表示边 v → w 的权重。

对应书本命题 P:

![image-20240315100652432]

必要性证明:

![image-20240315101018144]

对应书本的证明:

![image-20240315101424511]

充分性证明:

![image-20240315101504323]

对应书本的证明:

![image-20240315101559185]

2.4:通用算法 generic shortest-paths algorithm

对应书本命题 Q:

![image-20240315102227890]

3:Dijkstra 算法

3.1:demo 演示

![image-20240315103616581]

  • 按照离源点 s 的距离递增顺序考虑顶点(选取具有最低 distTo[] 值的非树顶点)。
  • 将该顶点添加至树结构中,并对其指向的所有边执行松弛操作。

初始状态:

![image-20240315103812262]

距离 s 最近是顶点 0,从顶点 0 开始:

![image-20240315103957761]

对从顶点 0 开始的边进行松弛操作:

![image-20240315104159042]

顶点 0 到 1 为最短路径,继续选择顶点 1:

![image-20240315110732282]

对从顶点 1 开始的边进行松弛操作:

![image-20240315110937592]

![image-20240315111120815]

顶点 0 到 7 为最短路径,继续选择顶点 7:

![image-20240315112458304]

对从顶点 7 开始的边进行松弛操作:

![image-20240315112525900]

![image-20240315112605879]

顶点 0 到 4 为最短路径,继续选择顶点 4:

![image-20240315112740572]

对从顶点 4 开始的边进行松弛操作:

![image-20240315112842144]

![image-20240315112904984]

顶点 4 到 5 为最短路径,继续选择顶点 5:

![image-20240315113029552]

对从顶点 5 开始的边进行松弛操作:

![image-20240315113110077]

![image-20240315113126024]

顶点 5 到 2 为最短路径,继续选择顶点 2:

![image-20240315113207365]

对从顶点 2 开始的边进行松弛操作:

![image-20240315113236950]

![image-20240315113249721]

顶点 2 到 3 为最短路径,继续选择顶点 3:

![image-20240315113329032]

对从顶点 3 开始的边进行松弛操作:

![image-20240315113348502]

![image-20240315113406022]

顶点 2 到 6 为最短路径,继续选择顶点 6:

![image-20240315113446235]

对从顶点 6 开始的边进行松弛操作:

![image-20240315113534275]

s 开始的最短路径树:

![image-20240315113948791]

3.2:证明

![L15-44ShortestPaths_29]

对应书本命题 R:

![image-20240315114148251]

3.3:Java 实现

edu.princeton.cs.algs4.DijkstraSP

![image-20240315115804455]

![image-20240315115855899]

edu.princeton.cs.algs4.DijkstraSP#relax

![image-20240315120026331]

3.4:计算图生成树

![L15-44ShortestPaths_33]

Dijkstra 算法应该相当熟悉吧?

  • Prim 算法在本质上是相同的算法。
  • 两者都属于计算生成树的一类算法。

主要区别在于 选择下一个加入树中的顶点时所依据的规则:

  • Prim 算法选择的是距离当前生成树最近的顶点(通过无向边);
  • 而 Dijkstra 算法选择的是距离源点最近的顶点(通过有向路径)。

注: 深度优先搜索(DFS)和广度优先搜索(BFS)也属于这一类用于生成树或遍历图的算法。

3.5:运行时间

(同 Prim 算法)

![L15-44ShortestPaths_32]

核心要点:

  • 采用数组实现对稠密图(Dense graphs)而言是最佳方案。
  • 对于稀疏图(Sparse graphs),二叉堆在性能上要快得多。
  • 在对性能要求极高的情况下,使用四路堆(4-way heap)是值得投入精力提升性能的。
  • 斐波那契堆在理论上的优越性虽高,但在实际开发中却未必值得进行具体实现。

4:无环加权有向图 edge-weighted DAGs

4.1:demo 演示

![image-20240316134718054]

  • 按拓扑排序考虑顶点。
  • 从该顶点出发对所有指向的边进行松弛操作。

初始状态:

![image-20240316134854048]

首先对顶点进行拓扑排序:

![image-20240316135043894]

从顶点 0 开始,对从顶点 0 开始的边进行松弛操作:

![image-20240316135324509]

继续选择顶点 1,并进行松弛操作:

![image-20240316135515915]

继续选择顶点 4,并进行松弛操作:

![image-20240316141338821]

继续选择顶点 7,并进行松弛操作:

![image-20240316141608117]

继续选择顶点 5,并进行松弛操作:

![image-20240316141644511]

继续选择顶点 2,并进行松弛操作:

![image-20240316141819644]

继续选择顶点 3,并进行松弛操作:

![image-20240316143812156]

继续选择顶点 6,并进行松弛操作:

![image-20240316143839873]

s 开始的最短路径树:

![image-20240316144501557]

4.2:证明

![L15-44ShortestPaths_38]

对应书本命题 S:

![image-20240316145708486]

4.3:Java 实现

edu.princeton.cs.algs4.AcyclicSP

![image-20240316151408099]

![image-20240316151431446]

4.4:最长路径

![L15-44ShortestPaths_46]

带权重有向无环图(DAG)中的最短路径问题:

  • 对所有边的权重取反。
  • 找出这些取反权重后的最短路径。
  • 在得到的结果中再次对边的权重取反。

(等价于:在 relax() 函数中反转相等性判断的方向)

关键点: 拓扑排序算法即使在存在负权边的情况下也能正常工作。

5:负权重 negative weights

5.1:失败尝试

![L15-44ShortestPaths_51]

Dijkstra 算法: 该算法无法处理具有负权重的边。
重赋权重法: 对所有边权重增加一个常数值的方法无效。
结论: 我们需要采用一种不同的算法来解决此问题。

5.2:负权重环 negative cycles

![L15-44ShortestPaths_52]

对应书本定义以及命题 W:

![image-20240316161032461]

![image-20240316161058157]

5.3:Bellman-Ford 算法

![L15-44ShortestPaths_53]

对应书本命题 X:

![image-20240316163337743]

5.3.1:demo 演示

![image-20240316163457806]

重复 V 次:松弛有向图 E 所有边。

初始状态:

![image-20240316163628062]

初始化,将到源的距离设置为 0:

![image-20240316163838365]

对顶点 0 所有有向边进行松弛操作:

![image-20240316164534404]

![image-20240316164759986]

![image-20240316164813178]

对顶点 1 所有有向边进行松弛操作:

![image-20240316164925311]

![image-20240316164943422]

![image-20240316165014037]

对顶点 2 所有有向边进行松弛操作:

![image-20240316165052683]

![image-20240316165128407]

对顶点 3 所有有向边进行松弛操作:

![image-20240316165152695]

对顶点 4 所有有向边进行松弛操作:

![image-20240316165252427]

![image-20240316165320702]

![image-20240316165349289]

对顶点 5 所有有向边进行松弛操作:

![image-20240316165439474]

![image-20240316165504694]

对顶点 7 所有有向边进行松弛操作:

![image-20240316165531693]

![image-20240316165552335]

以上完成第一轮操作。

再次进行松弛操作。

大部分操作与第一轮类似,但也有可以更新的部分:

![image-20240316165907917]

![image-20240316170050428]

同理进行后续的循环:

![image-20240316170146032]

没有更加优化的路径,完成所有松弛操作。

最终得到 s 开始的最短路径树:

![image-20240316170308062]

5.3.2:算法分析

![L15-44ShortestPaths_57]

对应书本命题 Y:

![image-20240316181217238]

5.4:成本开销小结

![L15-44ShortestPaths_59]

  • 注释1: 存在有向循环会使问题求解难度增大。
  • 注释2: 负权重边的存在会使问题变得更加复杂。
  • 注释3: 负权重环会导致问题无法有效解决或无解状态。

6:小结

![L15-44ShortestPaths_65]

非负权重:

  • 在许多应用中出现。
  • Dijkstra 算法的时间复杂度接近线性时间。

无环带权有向图:

  • 在某些应用中出现。
  • 通过拓扑排序算法可以在线性时间内求解。
  • 边的权重可以为负。

负权重和负权重环:

  • 在某些应用中出现。
  • 如果不存在负权重环,可以通过 Bellman-Ford 算法找到最短路径。
  • 若存在负权重环,仍可通过 Bellman-Ford 算法找到一条路径(但可能不是最短路径)。

最短路径问题是广泛应用于问题求解的一个模型。

![image-20240316183053632]

(完)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/461919.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Unity类银河恶魔城学习记录10-12 p100 Improve aliments - chill源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili CharacterStats.cs using System.Collections; using System.Collections…

docker容器镜像管理

目录 一、 Docker的基本组成 二、 容器和镜像的关系 2.1 面向对象角度 2.2 从镜像容器角度 三、镜像命令 3.1 查看当前已有镜像 3.2 查看已有的全部镜像 3.3 查看镜像ID 3.4 镜像删除 四、 容器命令 4.1 下载镜像 4.2 新建和启动容器 run 4.3 交互式 4.…

探讨大世界游戏的制作流程及技术——大场景制作技术概况篇

接上文,我们接下来了解一下大世界场景制作技术有哪些,本篇旨在给大家过一遍目前业界的做法,能让大家有一个宏观的知识蓝图。实际上,针对不同的游戏类型和美术风格,制作技术在细节上有着非常大的不同,业界目…

【UE5】持枪状态站立移动的动画混合空间

项目资源文末百度网盘自取 创建角色在持枪状态站立移动的动画混合空间 在BlendSpace文件夹中单击右键选择动画(Animation)中的混合空间(Blend Space) 选择SK_Female_Skeleton 命名为BS_RifleStand 打开 水平轴表示角色的方向,命名为Direction,方…

SD-WAN技术助力跨境电商网络搭建的解决方案

随着全球贸易的蓬勃发展,跨境电商成为了商业领域中的一个重要组成部分。然而,跨境电商面临着网络搭建和管理的复杂性,而SD-WAN技术的引入为解决这些问题提供了一种创新的方法。本文将深入探讨SD-WAN如何有效解决跨境电商行业的网络搭建问题。…

UE5.1 iClone8 正确导入角色骨骼与动作

使用iClone8插件Auto Setup 附录下载链接 里面有两个文件夹,使用Auto Setup C:\Program Files\Reallusion\Shared Plugins 在UE内新建Plugins,把插件复制进去 在工具栏出现这三个人物的图标就安装成功了 iClone选择角色,导入动作 选择导出FBX UE内直接导入 会出现是否启动插件…

同城预约上门服务APP小程序开发 打造快捷便利生活

随着移动互联网的快速发展,人们的生活方式正在发生深刻的变化。特别是在城市生活中,人们越来越依赖移动应用来解决日常生活中的各种问题。其中,同城预约上门服务APP正成为一种新型的生活服务平台,为人们提供了更加便利和快捷的服务…

RTC的Google拥塞控制算法 rmcat-gcc-02

摘要 本文档描述了使用时的两种拥塞控制方法万维网(RTCWEB)上的实时通信;一种算法是基于延迟策略,一种算法是基于丢包策略。 1.简介 拥塞控制是所有共享网络的应用程序的要求互联网资源 [RFC2914]。 实时媒体的拥塞控制对于许…

2023年总结:一个普通程序员如何挑选出价值千万的职业赛道

​​​​​​​ 引言 随着2023年的序幕缓缓落下,我终于在岁月的流转中捕捉到了一条隐秘而又公开的真理。它悄然告诉我们,成功并非单纯由勤劳的双手雕琢,一份耕耘未必有一份收获,而是在于我们如何在命运的十字路口作出关键选择。那…

Linux/secret

Enumeration nmap 第一次扫描发现系统对外开放了22,80和3000端口,端口详细信息如下 可以看到22端口对应的是ssh服务,80和3000都是http服务,80端口使用nginx,3000使用了Node.js TCP/80 可以先从80端口开始探索&…

滑动窗口和螺旋矩阵

209. 长度最小的子数组 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续 子数组 [numsl, numsl1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回…

R统计学3 - 数据分析入门问题41-60

往期R统计学文章: R统计学1 - 基础操作入门问题1-20 R统计学2 - 数据分析入门问题21-40 41. R 语言如何做双坐标图? # 创建模拟数据 year <- 2014:2024 gdp <- data.frame(year, GDP = sort(rnorm(11, 1000, 100))) ur <- data.frame(year, UR = rnorm(11, 5, 1…

微信小程序原生<map>地图实现标记多个位置以及map 组件 callout 自定义气泡

老规矩先上效果图: 1 、在pages文件夹下新建image文件夹用来存放标记的图片。 2、代码片段 也可以参考小程序文档:https://developers.weixin.qq.com/miniprogram/dev/component/map.html index.wxml代码 <mapid="map"style="width: 100%; height:100%;&…

外包就干了2个月,技术退步明显....

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…

分布式机器学习

考虑到当今大数据时代生成的数据量&#xff0c;分布式机器学习是一项重要技术。 由此引出的问题是&#xff0c;我们应该选择哪个平台来帮助构建分布式机器学习环境&#xff1f; Apache Spark 是近年来非常流行的此类平台之一。 spark Apache Spark 是一个开源集群计算框架&am…

MySQL语法分类 DDL(2)

DDL&#xff08;2&#xff09; C(Create):创建 //复制表 create table 表名 like 被复制的表名;//数据类型 1. int : 整数类型 2. double : 小数类型 //double(5,2) 最多五位且保留两位小数 3. date : 日期类型 //只包含年月日 yyyy-MM-dd 4. datetime : 日期 //包含年月日时…

php彩虹/异世界云商全解系统

系统更新与修复列表 1. 基于彩虹的二次开发 - 对彩虹系统进行了二次开发&#xff0c;增强了系统的功能和性能。2. 新增自定义输入框提示内容&#xff08;支持批量修改&#xff09; - 用户可以自定义输入框的提示内容&#xff0c;并支持批量修改&#xff0c;提升用户体验。3. 新…

DFS的一些题目

题目1&#xff1a;奶牛选美 这道题其实就是把两个连通块合成一个&#xff0c;可以用dfs、bfs和并查集。因为最近在dfs专题训练&#xff0c;这里我只写了dfs。 首先我们用dfs的方式遍历两个连通块&#xff0c;将两个连通块中点的坐标分别存入两个数组中&#xff0c;将这两个数组…

AI预测福彩3D第10弹【2024年3月16日预测--第2套算法重新开始计算第2次测试】

今天继续开始咱们第2套算法的验证&#xff0c;计划每套算法连续测试10期&#xff0c;达到50%的命中率即为较优的模型&#xff0c;可继续使用。老规矩&#xff0c;先上图表&#xff0c;再下结论~ 最终&#xff0c;经过研判分析&#xff0c;2024年3月16日福彩3D的七码预测结果如下…

LeetCode 面试经典150题 26.删除有序数组中的重复项

题目&#xff1a; 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量…