当前位置: 首页 > news >正文

图的最短路径算法:Dijkstra、Floyd-Warshall、Bellman-Ford

本文意在探讨图中最短路径算法 Dijkstra、Floyd-Warshall、Bellman-Ford 的对比和细节

整体分为如下四部分

  1. 总结性的比较了 Dijkstra、Floyd-Warshall、Bellman-Ford
  2. Dijkstra 算法介绍
  3. Floyd-Warshall 算法介绍
  4. Bellman-Ford 算法介绍

其中1、2、3 算法介绍部分会比较简洁,整体而言 Dijkstra 算法相对来说较难理解,而 Floyd-Warshall、Bellman-Ford 通过伪代码可以快速理解其含义

建议可以先快速浏览 0,然后看 2、3、1,再阅读一次 0

0 最短路径中:Dijkstra、Floyd-Warshall、Bellman-Ford 算法比较的 Cheat Sheet

比较维度DijkstraFloyd-WarshallBellman-Ford
最佳用途寻找地图上点到点的最短路计算网络中所有点对的最短路路径规划/网络优化,尤其是存在负权边时
目标单源最短路径所有节点对的最短路径单源最短路径
时间复杂度O(V^2) 或 O(E + V log V)O(V^3)O(VE)
空间复杂度O(V)O(V^2)O(V)
负权边不支持(仅正权边)支持(但不支持负权环)支持(且能检测负权环)
底层数据结构优先队列/堆二维数组数组
是否适用于分布式
算法类型贪心算法动态规划动态规划
实现难度中等简单简单
更新策略单点更新全局更新单点更新
路径重构直接通过前置节点通过中间节点递归构建直接通过前置节点

0.A 关于上面表格的问题 1

“是否适用于分布式” 是什么含义

0.A 问题 1 的回答

在这里,“是否适用于分布式”指的是算法是否能够被有效地实施在一个分布式计算环境中,也就是多个计算节点分别进行计算的情况。

对于分布式环境,算法能否被分解成可以在网络中不同节点上独立运行的子过程是一个重要的考量。在这样的环境中,节点通常只拥有局部的信息,而不是整个网络的全局信息,并且需要通过消息传递来协调解决方案。

例如,Bellman-Ford算法可以被用在分布式系统中,每个节点可以独立地运行算法的一部分,并通过网络与其他节点交换信息。这个特性使其适用于如路由协议之类的分布式网络应用,如RIP(Routing Information Protocol)。

相比之下,Dijkstra算法和Floyd-Warshall算法通常在一个单一的计算实体上执行,并需要有关全局网络的全部信息,所以它们在标准形式下不适用于分布式环境。然而,Dijkstra算法也有可能被修改为一个分布式版本,如在OSPF(Open Shortest Path First)路由协议中使用的那样。

0.B 关于上面表格的问题 2

Floyd-Warshall、Bellman-Ford 这两个算法是基于动态规划

我的知识储备中,动态规划需要满足最优子结构和重叠子问题两个特征,这两个算法是如何满足动态规划特性的

0.B 问题 2 的回答

Floyd-Warshall算法和Bellman-Ford算法确实是基于动态规划思想设计的,下面解释它们是如何满足动态规划特性的:

  • Floyd-Warshall算法
    • 最优子结构:Floyd-Warshall算法的最优子结构体现在计算任意两点i和j之间的最短路径时,可以通过包含中间节点k的子路径来实现。如果已知从i到k和从k到j的最短路径,那么可以通过它们来构建从i到j的最短路径。算法本质上是在尝试通过加入更多的中间节点来不断更新两点之间的最短路径。
    • 重叠子问题:在计算节点对之间的最短路径时,算法重复解决了许多相同的子问题。例如,在计算从i到j的最短路径时,需要用到从i到其他所有节点以及从所有节点到j的最短路径信息,而这些信息在计算其他节点对之间的最短路径时会重复使用。
  • Bellman-Ford算法
    • 最优子结构:Bellman-Ford算法利用的最优子结构是指从源点到目标点的最短路径可以通过一系列的最短路径决策来构建。如果已知从源点到节点u的最短路径,并且存在一条边从u到v,那么只有当从源点经u到v的路径比已知的从源点到v的路径更短时,才更新源点到v的距离。
    • 重叠子问题:在更新节点间最短路径的过程中,算法会在每次迭代中对所有边进行松弛操作。每次更新一个节点的最短路径估计时,都可能用到其他节点的最短路径估计,这些估计在算法的多个迭代中被重复计算和使用。

在这两个算法中,动态规划的思想通过构建表格(在Floyd-Warshall算法中是一个二维表格,而在Bellman-Ford算法中通常是一维数组)来保存子问题的解决方案,并通过这些已解决的子问题来解决更大的问题。这些表格存储了算法的中间结果,使得每个子问题只需要计算一次,从而避免了重复计算。

1. Dijkstra 算法

算法概览:在图中找到从源点到其他所有点的最短路径,通过为每个顶点维护一个最短路径估计,并逐渐更新这些估计,直到找到最短路径。

伪代码

function Dijkstra(Graph, source):dist[source] ← 0                           // 初始化源点到自己的距离为0for each vertex v in Graph:                 // 对图中每个顶点if v ≠ sourcedist[v] ← ∞                         // 初始化源点到每个顶点的距离为无穷大prev[v] ← undefined                     // 前置节点初始化为未定义Q ← the set of all nodes in Graph           // 将所有节点加入队列while Q is not empty:                       // 当队列非空时循环u ← vertex in Q with min dist[u]        // 从Q中找出距离最小的顶点uremove u from Q                         // 从Q中移除顶点ufor each neighbor v of u:               // 遍历u的所有邻居alt ← dist[u] + length(u, v)        // 计算经u到邻居v的距离if alt < dist[v]:                   // 如果经u到v的距离更短dist[v] ← alt                   // 更新距离prev[v] ← u                     // 更新前置节点为ureturn dist, prev                           // 返回所有节点的最短距离以及路径

在此伪代码中,Graph 表示图,source 表示源点,dist 表示从源点到每个顶点的距离,prev用来记录最短路径上的前置节点。Q 是一个优先队列,用来找出当前未处理的最近的顶点。length(u, v) 是边 (u, v) 的权重。这个算法假设图中所有边的权重都是非负的。

2. Floyd-Warshall算法

算法概览:核心思想是通过迭代过程,考虑将所有其他顶点作为中间顶点来更新每对顶点之间的最短路径

伪代码

function FloydWarshall(W)n := length(W) // W is the graph represented as an adjacency matrixD := W        // D is a distance matrix that will be updatedfor k from 1 to nfor i from 1 to nfor j from 1 to nif D[i][k] + D[k][j] < D[i][j] thenD[i][j] := D[i][k] + D[k][j]return D

在这里,W 是一个邻接矩阵,表示图中所有顶点之间的权重(或距离)。如果不存在直接的边,那么W[i][j] 应该是一个非常大的数(代表无穷)。D 是 Floyd-Warshall 算法计算过程中的距离矩阵,最后会变成所有顶点对之间最短路径的长度。在伪代码中,n 是顶点的数目。

疑问

算法中的 i j k 循环顺序可以调整吗

解答

Floyd-Warshall 算法中的三个循环 (i, j, k) 的顺序是可以互换的,但通常 k 循环是放在最外层的。在算法的迭代过程中,k 循环代表的是允许作为中介点的顶点集合的逐步扩大。换句话说,算法首先计算只允许使用顶点 1 作为中介的所有最短路径,然后是顶点 1 和 2,依此类推,直到考虑所有顶点作为中介点。

k 循环放在最外层确保了在更新 D[i][j] 时,考虑的所有中间顶点都是在之前的迭代中已经处理过的。如果 ij 循环在 k 循环的外面,算法就不能保证这一点,可能会导致不正确的结果。

因此,k 循环必须保持在最外层,而 ij 循环的顺序可以互换,因为它们只是在独立地更新两点之间的最短距离。

3. Bellman-Ford 算法

算法概览:通过对图中所有边进行重复松弛操作,以计算图中单个源点到其他所有点的最短路径,能够处理包含负权边的图。

伪代码

function BellmanFord(vertices, edges, source):// 初始化距离数组,将源点到所有点的距离设为无穷大,除了源点自身设为0distance := array of size |vertices|, fill with ∞ (infinity)distance[source] := 0// 循环|V|-1次,V是顶点数量for i from 1 to |vertices|-1:// 对每条边进行一次松弛操作for each edge (u, v, w) in edges:if distance[u] + w < distance[v]:distance[v] := distance[u] + w// 检测负权重循环// 再次对所有边进行检查,如果还能找到更短的路径,则存在负权重循环for each edge (u, v, w) in edges:if distance[u] + w < distance[v]:// 如果这里的条件为真,则图中存在从源点可达的负权重循环return "Graph contains a negative-weight cycle"return distance

疑问 1

for i from 1 to |vertices|-1:// 对每条边进行一次松弛操作for each edge (u, v, w) in edges:
...

这里的 (u, v, w) 和外层循环 for i from 1 to |vertices|-1 有什么关系吗

u, v 需要是外层顶点循环中的一个吗

疑问 1 的回答

在贝尔曼-福特算法的伪代码中,(u, v, w) 表示一条边,其中 u 是起点,v 是终点,w 是这条边的权重。

这些边和外层顶点循环 for i from 1 to |vertices|-1 并没有直接的对应关系,也就是说,uv 不需要是外层顶点循环中的特定顶点。

外层的循环 for i from 1 to |vertices|-1 的目的是重复尝试“松弛”操作足够多的次数,确保算法能正确处理所有的最短路径,即使这些路径可能通过多个顶点。在无负权重循环的情况下,任何最短路径最多包含 |vertices|-1 条边。因此,重复进行 |vertices|-1 次遍历所有边并尝试进行松弛操作,足以保证算法找到所有可能的最短路径。

内层循环 for each edge (u, v, w) in edges 则是负责实际的松弛操作,它会检查图中的每一条边,无论这些边的起点和终点是什么。每次内层循环时,算法会尝试更新从起点 u 到终点 v 的最短路径估计。

简而言之,外层循环确保算法有足够的迭代次数来处理所有的最短路径,而内层循环则是对具体的边进行操作,两者各自独立,共同配合完成算法的整个过程。

疑问 2

看起来 for each edge (u, v, w) in edges 中,uv 是可以对换的,所以 distance[u] + w < distance[v] 为何不需要再判断 distance[v] + w < distance[u]

疑问 2 的回答

for each edge (u, v, w) in edges 这个循环中,uv 代表边的起点和终点,它们并不是可以随意对换的。

  • 有向图中
    • 边是有方向的,从 uv 可能与从 vu 的距离不同,因为可能存在一条从 uv 的边,但不一定存在反方向的边,即便存在,其权重 w 也可能不同。
    • 算法中的 distance[u] + w < distance[v] 这个条件是在尝试进行松弛操作,意思是:如果你可以通过点 u 到达点 v,并且这样做得到的路径比你目前记录的到点 v 的路径更短,那么就更新到点 v 的最短路径距离。这是一个单向的检查。
  • 无向图中
    • 通常在输入的边集 edges 中,每条无向边会被转换成两条有向边,即一条从 uv,另一条从 vu,它们的权重是相同的。这样,算法在遍历边的时候自然会检查每个方向的距离。
    • 因此,不需要额外再判断 distance[v] + w < distance[u],因为算法会在遍历到边 (v, u, w') 时自然地处理这种情况,其中 w' 是从 vu 的边的权重。在无向图中 w'w 是相同的,在有向图中则可能不同。这保证了算法考虑了所有方向的边。

相关文章:

图的最短路径算法:Dijkstra、Floyd-Warshall、Bellman-Ford

本文意在探讨图中最短路径算法 Dijkstra、Floyd-Warshall、Bellman-Ford 的对比和细节 整体分为如下四部分 总结性的比较了 Dijkstra、Floyd-Warshall、Bellman-FordDijkstra 算法介绍Floyd-Warshall 算法介绍Bellman-Ford 算法介绍 其中1、2、3 算法介绍部分会比较简洁&…...

Camera的pipline(TODO)

&#xff08;TODO&#xff09;...

非关系数据库-非关系数据库入门指南

非关系数据库入门指南 1. 引言&#xff1a;非关系数据库的兴起​ 在互联网技术飞速发展的今天&#xff0c;传统的关系型数据库面对海量数据和高并发访问时逐渐显得力不从心。于是&#xff0c;非关系数据库&#xff08;NoSQL&#xff0c;Not Only SQL&#xff09;应运而生&…...

看门狗IWDG、WWDG(速记版)

内置的看门狗有 独立看门狗 IWDG 和 窗口看门狗 WWDG 都用来在程序卡死的时候复位程序。 独立看门狗只有一个最晚时间界限。窗口看门狗有一个最早界限和最晚界限。独立看门狗有独立的时钟,一般设置来源时钟LSI40KHz。窗口看门狗挂靠在APB1总线上36MHz。 IWDG IWDG处于VDD供…...

ETL工程师角度下的SQL优化

作为ETL&#xff08;Extract, Transform, Load&#xff09;工程师&#xff0c;SQL优化是提高数据处理和分析效率的关键一环。优化SQL查询可以显著降低数据处理时间&#xff0c;提高ETL过程的性能。本文将从 合理设计数据模型&#xff1a;在ETL过程中&#xff0c;正确的数据模型…...

阿里云实时计算Flink在多行业的应用和实践

摘要&#xff1a;本文整理自 Flink Forward Asia 2023 中闭门会的分享。主要分享实时计算在各行业的应用实践&#xff0c;对回归实时计算的重点场景进行介绍以及企业如何使用实时计算技术&#xff0c;并且提供一些在技术架构上的参考建议。内容分为以下四个部分&#xff1a; 业…...

开源项目与工具:C++中的高性能并发库 - Intel Threading Building Blocks (TBB)

在C++的世界里,随着多核处理器成为常态,如何有效利用这些多核资源以实现高性能的并发编程成为了开发者们关注的焦点。Intel Threading Building Blocks (TBB) 作为一个专为并行编程设计的C++库,凭借其易用性、高效性和可扩展性,在高性能计算、游戏开发、金融分析等多个领域…...

Chapter 22 数据可视化——折线图

欢迎大家订阅【Python从入门到精通】专栏&#xff0c;一起探索Python的无限可能&#xff01; 文章目录 前言一、Pyecharts介绍二、安装Pyecharts三、全局配置项四、绘制折线图 前言 在大数据时代&#xff0c;数据可视化成为了分析和展示数据的重要手段。Pyecharts 是一个基于 …...

管理流创建schema流程源码解析

一、简析 schema是pulsar重要的功能之一&#xff0c;现在就一起从源码的视角看下管理流创建schema时客户端和服务端的表现 客户端 客户端主要经历以下四个步骤 创建Schema实例 根据数据类型创建相对应的实例&#xff0c;例如Avro创建AvroSchema、JSON创建JSONSchema等 获取…...

【iOS】iOS内存五大分区

iOS内存五大分区 总揽 iOS中&#xff0c;内存主要分为五大区域&#xff1a;栈区&#xff0c;堆区&#xff0c;全局区/静态区&#xff0c;常量区和代码区。总览图如下。 这个图我觉得更好记&#xff0c;因为下面是低地址&#xff0c;上面是高地址&#xff0c;是比较符合日常…...

【项目实战】—— 高并发内存池

文章目录 什么是高并发内存池&#xff1f;项目介绍一、项目背景二、项目目标三、核心组件四、关键技术五、应用场景六、项目优势 什么是高并发内存池&#xff1f; 高并发内存池是一种专门设计用于高并发环境下的内存管理机制。它的原型是Google的一个开源项目tcmalloc&#xff…...

二叉搜索树的第 k 大的节点

题目描述 给定一棵二叉搜索树&#xff0c;请找出其中第 k 大的节点。 解题基本知识 二叉搜索树&#xff08;Binary Search Tree&#xff09;又名二叉查找树、二叉排序树。它是一棵空树&#xff0c;或者是具有下列性质的二叉树&#xff1a; 若它的左子树不空&#xff0c;则左子…...

利用langchain 做大模型 Few-shot Learning 提示,包括固定和向量相似的动态样本筛选

文章目录 few-shotFixed Examples 固定样本Dynamic few-shot prompting 动态样本提示辅助参考资料 few-shot 相比大模型微调&#xff0c;在有些情况下&#xff0c;我们更想使用 Few-shot Learning 通过给模型喂相关样本示例&#xff0c;让模型能够提升相应任务的能力。 固定样…...

基于python的百度迁徙迁入、迁出数据分析(五)

终于在第五篇文章我们进入了这个系列的正题&#xff1a;数据分析 这里我选择上海2024年5月1日——5月5日的迁入、迁出数据作为分析的基础&#xff0c;首先选择节假日的数据作为分析的原因呢&#xff0c;主要是节假日人们出行目的比较单一&#xff08;出游、探亲&#xff09;&a…...

SpringBoot 如何处理跨域请求

SpringBoot 处理跨域请求&#xff0c;通常是通过配置全局的 CORS&#xff08;跨源资源共享&#xff09;策略来实现的。CORS 是一种机制&#xff0c;它使用额外的 HTTP 头部来告诉浏览器&#xff0c;让运行在一个 origin (domain) 上的 web 应用被准许访问来自不同源服务器上的指…...

大数据技术基础编程、实验和案例----大数据课程综合实验案例

一、实验目的 (1&#xff09;熟悉Linux系统、MySQL、Hadoop、HBase、Hive、Sqoop、R、Eclipse等系统和软件的安装和使用&#xff1b; (2&#xff09;了解大数据处理的基本流程&#xff1b; (3&#xff09;熟悉数据预处理方法&#xff1b; (4&#xff09;熟悉在不同类型数据库之…...

微信小程序-获取手机号:HttpClientErrorException: 412 Precondition Failed: [no body]

问题&#xff1a; 412 异常就是你的请求参数获取请求头与服务器的不符&#xff0c;缺少请求体&#xff01; 我的问题&#xff1a; 我这里获取微信手机号的时候突然给我报错142&#xff0c;但是代码用的是原来的代码&#xff0c;换了一个框架就噶了&#xff01; 排查问题&am…...

大数据核心概念与技术架构简介

大数据基本概念 大数据是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合&#xff0c;是具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。 大数据特征&#xff1a; 数据量大&#xff1a;一般以P&#xff08;1000个TB&a…...

快排 谁在中间

原题 Whos in the Middle FJ is surveying his herd to find the most average cow. He wants to know how much milk this median cow gives: half of the cows give as much or more than the median; half give as much or less. FJ正在调查他的牛群&#xff0c;以找到最…...

ORA-00911: invalid character

场景&#xff1a; 调用接口查询oracle的数据库数据时报错ORA-00911: invalid character&#xff0c;但是sql语句没有问题放在navicat控制台中运行也没有问题&#xff0c;但是代码中跑就会报无效字符集 分析&#xff1a; 代码中Oracle的语法解析器比较严格&#xff0c;比如句…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...