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

最短路径算法:Floyd-Warshall算法

引言

在图论中,Floyd-Warshall算法是一种用于计算任意两点之间最短路径的动态规划算法。它适用于加权有向图和无向图,可以处理带有负权重边的图,但要求图中不能有负权重环。本文将详细介绍Floyd-Warshall算法的定义、步骤及其实现。

Floyd-Warshall算法

定义

Floyd-Warshall算法是一种用于计算图中所有顶点对之间最短路径的算法。该算法利用动态规划的思想,通过不断更新顶点对之间的最短路径,最终得到所有顶点对的最短路径矩阵。

算法步骤

  1. 初始化:创建一个距离矩阵dist,其中dist[i][j]表示顶点i到顶点j的初始距离。如果i和j之间有边,则dist[i][j]为边的权重;如果i和j之间没有边且i≠j,则dist[i][j]为正无穷大;如果i=j,则dist[i][j]为0。
  2. 更新距离矩阵:对于每一对顶点(i, j),通过中间顶点k更新其最短路径。具体来说,如果dist[i][j] > dist[i][k] + dist[k][j],则更新dist[i][j] = dist[i][k] + dist[k][j]。
  3. 重复更新:重复上述步骤,直到所有顶点对之间的最短路径都被计算出来。

示例

假设我们有一个带权有向图,顶点集合为 ({A, B, C, D}),边和权重集合为 ({(A, B, 3), (A, C, 8), (A, D, -4), (B, D, 1), (B, C, -2), (C, A, 4), (D, C, 7), (D, B, -5)})。

3
8
-4
1
-2
4
7
-5
A
B
C
D

Floyd-Warshall算法图解

  1. 初始化距离矩阵
  A   B   C   D
A 0   3   8  -4
B ∞   0  -2   1
C 4  ∞   0  ∞
D ∞  -5   7   0
  1. 通过顶点A更新距离矩阵
  A   B   C   D
A 0   3   8  -4
B 7   0  -2   1
C 4  ∞   0  ∞
D 3  -5   7   0
  1. 通过顶点B更新距离矩阵
  A   B   C   D
A 0   3   1  -4
B 5   0  -2   1
C 4  7   0  ∞
D 3  -5   2   0
  1. 通过顶点C更新距离矩阵
  A   B   C   D
A 0   3   1  -4
B 5   0  -2   1
C 4  7   0  ∞
D 3  -5   2   0
  1. 通过顶点D更新距离矩阵
  A   B   C   D
A 0  -1   1  -4
B 5   0  -2   1
C 4  -1   0  -3
D 3  -5   2   0

Floyd-Warshall算法实现

下面是用Java实现Floyd-Warshall算法的代码示例:

import java.util.Arrays;public class FloydWarshallAlgorithm {private static final int INF = 99999; // 表示无穷大的值// 计算任意两点之间的最短路径public void floydWarshall(int[][] graph) {int vertices = graph.length;int[][] dist = new int[vertices][vertices];// 初始化距离矩阵for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {dist[i][j] = graph[i][j];}}// 更新距离矩阵for (int k = 0; k < vertices; k++) {for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}printSolution(dist);}// 打印最短路径矩阵private void printSolution(int[][] dist) {int vertices = dist.length;System.out.println("顶点对之间的最短路径矩阵:");for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {if (dist[i][j] == INF) {System.out.print("INF ");} else {System.out.print(dist[i][j] + "   ");}}System.out.println();}}public static void main(String[] args) {int[][] graph = {{0, 3, 8, -4},{INF, 0, -2, 1},{4, INF, 0, INF},{INF, -5, 7, 0}};FloydWarshallAlgorithm floydWarshall = new FloydWarshallAlgorithm();floydWarshall.floydWarshall(graph);}
}

代码注释

  1. 常量定义

    private static final int INF = 99999; // 表示无穷大的值
    

    INF 表示无穷大,用于表示顶点之间没有直接连接。

  2. Floyd-Warshall算法

    public void floydWarshall(int[][] graph) {int vertices = graph.length;int[][] dist = new int[vertices][vertices];// 初始化距离矩阵for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {dist[i][j] = graph[i][j];}}// 更新距离矩阵for (int k = 0; k < vertices; k++) {for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}printSolution(dist);
    }
    

    floydWarshall 方法实现了Floyd-Warshall算法,计算任意两点之间的最短路径。

  3. 打印最短路径矩阵

    private void printSolution(int[][] dist) {int vertices = dist.length;System.out.println("顶点对之间的最短路径矩阵:");for (int i = 0; i < vertices; i++) {for (int j = 0; j < vertices; j++) {if (dist[i][j] == INF) {System.out.print("INF ");} else {System.out.print(dist[i][j] + "   ");}}System.out.println();}
    }
    

    printSolution 方法用于打印最短路径矩阵。

结论

通过上述讲解和实例代码,我们详细展示了Floyd-Warshall算法的定义、步骤及其实现。Floyd-Warshall算法是一种重要的最短路径算法,适用于计算任意两点之间的最短路径。希望这篇博客对您有所帮助!


如果您觉得这篇文章对您有帮助,请关注我的CSDN博客,点赞并收藏这篇文章,您的支持是我持续创作的动力!


关键内容总结

  • Floyd-Warshall算法的定义
  • Floyd-Warshall算法的步骤
  • Floyd-Warshall算法的实现及其

代码注释


推荐阅读:深入探索设计模式专栏,详细讲解各种设计模式的应用和优化。点击查看:深入探索设计模式。


特别推荐:设计模式实战专栏,深入解析设计模式的实际应用,提升您的编程技巧。点击查看:设计模式实战。

如有任何疑问或建议,欢迎在评论区留言讨论。谢谢阅读!

相关文章:

最短路径算法:Floyd-Warshall算法

引言 在图论中&#xff0c;Floyd-Warshall算法是一种用于计算任意两点之间最短路径的动态规划算法。它适用于加权有向图和无向图&#xff0c;可以处理带有负权重边的图&#xff0c;但要求图中不能有负权重环。本文将详细介绍Floyd-Warshall算法的定义、步骤及其实现。 Floyd-…...

3DM游戏运行库合集离线安装包2024最新版

3DM游戏运行库合集离线安装包是一款由国内最大的游戏玩家论坛社区3DM推出的集成式游戏运行库合集软件&#xff0c;旨在解决玩家在玩游戏时遇到的运行库缺失或错误问题。该软件包含多种常用的系统运行库组件&#xff0c;支持32位和64位操作系统&#xff0c;能够自动识别系统版本…...

【Bigdata】什么是混合型联机分析处理

这是我父亲 日记里的文字 这是他的生命 留下留下来的散文诗 几十年后 我看着泪流不止 可我的父亲已经 老得像一个影子 &#x1f3b5; 许飞《父亲写的散文诗》 混合型联机分析处理&#xff08;Hybrid OLAP&#xff0c;简称 HOLAP&#xff09;是一种结合了多…...

Java 并发编程:volatile 关键字介绍与使用

大家好&#xff0c;我是栗筝i&#xff0c;这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 026 篇文章&#xff0c;在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验&#xff0c;并希望进…...

【Spark计算引擎----第三篇(RDD)---《深入理解 RDD:依赖、Spark 流程、Shuffle 与缓存》】

前言&#xff1a; &#x1f49e;&#x1f49e;大家好&#xff0c;我是书生♡&#xff0c;本阶段和大家一起分享和探索大数据技术Spark—RDD&#xff0c;本篇文章主要讲述了&#xff1a;RDD的依赖、Spark 流程、Shuffle 与缓存等等。欢迎大家一起探索讨论&#xff01;&#xff0…...

四、日志收集loki+ promtail+grafana

一、简介 Loki是受Prometheus启发由Grafana Labs团队开源的水平可扩展&#xff0c;高度可用的多租户日志聚合系统。 开发语言: Google Go。它的设计具有很高的成本效益&#xff0c;并且易于操作。使用标签来作为索引&#xff0c;而不是对全文进行检索&#xff0c;也就是说&…...

xdma的linux驱动编译给arm使用(中断检测-测试程序)

1、驱动链接 XDMA驱动源码官网下载地址为&#xff1a;https://github.com/Xilinx/dma_ip_drivers 下载最新版本的XDMA驱动源码&#xff0c;即master版本&#xff0c;否则其驱动用不了&#xff08;xdma ip核版本为4.1&#xff09;。 2、驱动 此部分来源于博客&#xff1a;xd…...

探索之路——初识 Vue Router:构建单页面应用的完整指南

目录 1. Vue Router 简介 2. 安装与配置 Vue Router 安装步骤 配置路由 3. 在 Vue 应用中使用路由 4. 进阶使用 路由守卫 懒加载 高级路由技术 嵌套路由 动态路由匹配 编程式的路由导航 路由懒加载 路由元信息 在现代前端开发中,单页面应用(SPA)因其出…...

传输层_计算机网络

文章目录 运输层UDPTCPTCP连接管理TCP三次握手TCP四次挥手 可靠机制流量控制拥塞控制 QUIC 运输层 网络层提供了主机之间的逻辑通信 运输层为运行在不同主机上的进程之间提供了逻辑通信 UDP(用户数据报协议)提供一种不可靠、无连接的服务&#xff0c;数据报 TCP(传输控制协议)…...

自动驾驶的六个级别是什么?

自动驾驶汽车和先进的驾驶辅助系统&#xff08;ADAS&#xff09;预计将帮助拯救全球数百万人的生命&#xff0c;消除拥堵&#xff0c;减少排放&#xff0c;并使我们能够在人而不是汽车周围重建城市。 自动驾驶的世界并不只由一个维度组成。从没有任何自动化到完整的自主体验&a…...

深度学习复盘与论文复现F

文章目录 1、Environment construction1.1 macos conda1.2 macos PyTorch1.3 iTerm settings1.4 install jupyter 2、beam search2.1 greedy search2.2 exhaustive search2.3 beam search 3、Attention score3.1 Masking softmax operation3.2 Additive attention3.3 Zoom dot …...

如何学习自动化测试工具!

要学习和掌握自动化测试工具的使用方法&#xff0c;可以按照以下步骤进行&#xff1a; 一、明确学习目标 首先&#xff0c;需要明确你想要学习哪种自动化测试工具。自动化测试工具种类繁多&#xff0c;包括但不限于Selenium、Appium、JMeter、Postman、Robot Framework等&…...

短信接口被恶意盗刷

短信接口被恶意盗刷是指攻击者通过各种手段&#xff0c;大量发送短信请求&#xff0c;导致短信资源被浪费&#xff0c;服务提供商可能面临经济损失&#xff0c;正常用户的服务也可能受到影响。以下是一些可能导致短信接口被恶意盗刷的原因和相应的解决方案&#xff1a; 原因&a…...

实验4-2-1 求e的近似值

//实验4-2-1 求e的近似值 /* 自然常数 e 可以用级数 11/1!1/2!⋯1/n!⋯ 来近似计算。 本题要求对给定的非负整数 n&#xff0c;求该级数的前 n1 项和。 输入格式:输入第一行中给出非负整数 n&#xff08;≤1000&#xff09;。 输出格式:在一行中输出部分和的值&#xff0c;保留…...

内网穿透--LCX+portmap转发实验

实验背景 通过公司带有防火墙功能的路由器接入互联网&#xff0c;然后由于私网IP的缘故&#xff0c;公网 无法直接访问内部web服务器主机&#xff0c;通过内网其它主机做代理&#xff0c;穿透访问内网web 服务器主机 实验设备 1. 路由器、交换机各一台 2. 外网 kali 一台&…...

缓存一致性问题

1. 引言 1.1 数据库与缓存的工程实践 在软件工程领域&#xff0c;数据库&#xff08;Database&#xff09;和缓存&#xff08;Cache&#xff09;是两种常见的数据存储解决方案&#xff0c;它们在系统架构中扮演着至关重要的角色。数据库是数据持久化的后端存储&#xff0c;它…...

【MYSQL】MYSQL逻辑架构

mysql逻辑架构分为3层 mysql逻辑架构分为3层 1). 连接层&#xff1a;主要完成一些类似连接处理&#xff0c;授权认证及相关的安全方案。 2). 服务层&#xff1a;在 MySQL据库系统处理底层数据之前的所有工作都是在这一层完成的&#xff0c;包括权限判断&#xff0c;SQL接口&…...

【Python】数据类型之字符串

本篇文章将继续讲解字符串其他功能&#xff1a; 1、求字符串长度 功能&#xff1a;len(str) &#xff0c;该功能是求字符串str的长度。 代码演示&#xff1a; 2、通过索引获取字符串的字符。 功能&#xff1a;str[a] str为字符串&#xff0c;a为整型。该功能是获取字符…...

c++编写java模式的线程类

在 C11 中&#xff0c;我们可以使用 <thread> 标准库来创建和管理线程。然而&#xff0c;C 不像 Java 那样提供一个内置的 Thread 类&#xff0c;而是提供了一个更底层的 API。下面是一个模拟 Java 中 Thread 类功能的 C11 实现。 我们将创建一个名为 SimpleThread 的类…...

vcpkg install libtorch[cuda] -allow-unsupported-compiler

在vcpkg中不懂如何使用 nvcc 的 -allow-unsupported-compiler, 所以直接注释了CUDA中对版本的检查代码. C:\Program Files\NVIDIA GPU Computing Toolkit\CUDA\v11.8\include\crt\host_config.h 奇了怪了,我是用的是vs2022,但是还是被检查为不支持的编译器!!! 可以试一下改这…...

Flink的DateStream API中的ProcessWindowFunction和AllWindowFunction两种用于窗口处理的函数接口的区别

目录 ProcessWindowFunction AllWindowFunction 具体区别 ProcessWindowFunction 示例 AllWindowFunction 示例 获取时间不同&#xff0c;一个数据产生的时间一个是数据处理的时间 ProcessWindowFunction AllWindowFunction 具体示例 ProcessWindowFunction 示例 Al…...

MATLAB中dmperm函数用法

目录 语法 说明 dmperm函数的功能是完成Dulmage-Mendelsohn 分解。 语法 p dmperm(A) [p,q,r,s,cc,rr] dmperm(A) 说明 如果列 j 与行 i 匹配&#xff0c;p dmperm(A) 得到的结果为向量 p&#xff0c;这样 p(j) i&#xff0c;如果列 j 与其不匹配&#xff0c;得到的结…...

苹果折叠屏设备:创新设计与技术突破

本文首发于公众号“AntDream”&#xff0c;欢迎微信搜索“AntDream”或扫描文章底部二维码关注&#xff0c;和我一起每天进步一点点 苹果折叠屏设备&#xff1a;创新设计与技术突破 在科技迅速发展的今天&#xff0c;苹果公司以其一贯的创新精神和对产品质量的严格把控&#x…...

C#加班统计次数

C#加班统计次数 运行环境&#xff1a;vs2022 .net 8.0 社区版 1、用C#语言&#xff1b;2、有界面上传Excel文件; 3、对Excel列&#xff08;部门、人员姓名、人员编号、考勤时间 &#xff09;处理&#xff1a;&#xff08;1&#xff09;按人员编号、考勤日期分组且保留原来字段&…...

【资治通鉴】“ 将欲取之、必先予之 “ 策略 ① ( 魏桓子 割让土地 | 资治通鉴原文分析 | 道德经、周书、吕氏春秋、六韬 中的相似策略 )

文章目录 一、" 将欲取之、必先予之 " 策略1、魏桓子 割让土地2、资治通鉴原文分析 二、" 将欲取之、必先予之 " 类似的原理1、将欲败之&#xff0c;必姑辅之&#xff1b;将欲取之&#xff0c;必姑与之 - 周书2、将欲歙之&#xff0c;必固张之&#xff0c;…...

Spring5 的日志学习

我们在使用 Spring5 的过程中会出现这样的现像&#xff0c;就是 Spring5 内部代码打印的日志和我们自己的业务代码打印日志使用的不是统一日志实现&#xff0c;尤其是在项目启动的时候&#xff0c;Spring5 的内部日志使用的是 log4j2&#xff0c;但是业务代码打印使用的可能是 …...

python爬虫实践

两个python程序的小实验&#xff08;附带源码&#xff09; 题目1 爬取http://www.gaosan.com/gaokao/196075.html 中国大学排名&#xff0c;并输出。提示&#xff1a;使用requests库获取页面的基本操作获取该页面&#xff0c;运用BeautifulSoup解析该页面绑定对象soup&#x…...

【前端面试】七、算法-数组展平

目录 1.判断数组 2.二维数组展平 3.多维数组展平 1.判断数组 // 判断数组console.log([].constructor Array);console.log( Array.isArray([]));console.log( [] instanceof Array);console.log(Object.prototype.toString.call([]) [object Array]); 2.二维数组展平 const…...

Laravel php框架与Yii php 框架的优缺点

Laravel和Yii都是流行的PHP框架&#xff0c;它们各自具有独特的优点和缺点。以下是对这两个框架优缺点的详细分析&#xff1a; Laravel PHP框架的优缺点 优点 1、设计思想先进&#xff1a;Laravel的设计思想非常先进&#xff0c;非常适合应用各种开发模式&#xff0c;如TDD&…...

使用 addRouteMiddleware 动态添加中间

title: 使用 addRouteMiddleware 动态添加中间 date: 2024/8/4 updated: 2024/8/4 author: cmdragon excerpt: 摘要&#xff1a;文章介绍了Nuxt3中addRouteMiddleware的使用方法&#xff0c;该功能允许开发者动态添加路由中间件&#xff0c;以实现诸如权限检查、动态重定向及…...