当前位置: 首页 > 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;比如句…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...