当前位置: 首页 > 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,但是还是被检查为不支持的编译器!!! 可以试一下改这…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础

第三周 Day 3 &#x1f3af; 今日目标 理解类&#xff08;class&#xff09;和对象&#xff08;object&#xff09;的关系学会定义类的属性、方法和构造函数&#xff08;init&#xff09;掌握对象的创建与使用初识封装、继承和多态的基本概念&#xff08;预告&#xff09; &a…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...