Floyd - Warshall算法

顶点

public class Vertex {String name;List<Edge> edges;// 拓扑排序相关int inDegree;int status; // 状态 0-未访问 1-访问中 2-访问过,用在拓扑排序
​// dfs, bfs 相关boolean visited;//是否被访问过
​// 求解最短距离相关private static final int INF = Integer.MAX_VALUE;int dist = INF;Vertex prev = null;public Vertex(String name){this.name = name;}public String getName{return name;}@Override public String toString(){return name + '('+dist+')';}@Overridepublic boolean euqals(Object o){if(this == o)return true;if(0==null||getClass()!=o.getClass())return false;Vertex vertex = (Vertex) o;return Objexts.equals(name,Vertex.name);}@Overridepublic int hashCode(){return name!=null?name.hashCode():0;}

public class Edge {
​Vertex linked;int weight;
​public Edge(Vertex linked) {this(linked, 1);}
​public Edge(Vertex linked, int weight) {this.linked = linked;this.weight = weight;}
}

 可以处理负边 但是不能处理负环

4+-2+2+-1=3 所以没有负环

public class FloydWarshall {public static void main(String[] args) {Vertex v1 = new Vertex("v1");Vertex v2 = new Vertex("v2");Vertex v3 = new Vertex("v3");Vertex v4 = new Vertex("v4");v1.edges = List.of(new Edge(v3, -2));v2.edges = List.of(new Edge(v1, 4), new Edge(v3, 3));v3.edges = List.of(new Edge(v4, 2));v4.edges = List.of(new Edge(v2, -1));List<Vertex> graph = List.of(v1, v2, v3, v4);/*k=0直接连通v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   3   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0看上面那副图的权重k=1 借助v1到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0k=2 借助v2到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  3   -1  1   0k=3 借助v3到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  0v2  4   0   2   4v3  ∞   ∞   0   2v4  3   -1  1   0k=4 借助v4到达其它顶点v1  v2  v3  v4v1  0   -1   -2  0v2  4   0   2   4v3  5   1   0   2v4  3   -1  1   0*/floydWarshall(graph);}static void floydWarshall(List<Vertex> graph) {int size = graph.size();//顶点个数int[][] dist = new int[size][size];Vertex[][] prev = new Vertex[size][size];//从哪里来// 1)初始化for (int i = 0; i < size; i++) {Vertex v = graph.get(i); // v1 (v3)内层循环顶点Map<Vertex, Integer> map = v.edges.stream().collect(Collectors.toMap(e -> e.linked, e -> e.weight));for (int j = 0; j < size; j++) {Vertex u = graph.get(j); // v3  外层循环顶点if (v == u) {dist[i][j] = 0;//相同顶点} else {dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);prev[i][j] = map.get(u) != null ? v : null;//更新上一个顶点}}}print(prev);// 2)看能否借路到达其它顶点/*v2->v1          v1->v?dist[1][0]   +   dist[0][0]dist[1][0]   +   dist[0][1]dist[1][0]   +   dist[0][2]dist[1][0]   +   dist[0][3]*/for (int k = 0; k < size; k++) {for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {
//                    dist[i][k]   +   dist[k][j] // i行的顶点,借助k顶点,到达j列顶点
//                    dist[i][j]                  // i行顶点,直接到达j列顶点if (dist[i][k] != Integer.MAX_VALUE &&dist[k][j] != Integer.MAX_VALUE &&dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];prev[i][j] = prev[k][j];}}}
//            print(dist);}print(prev);for(int i=0;i<size;i++){for(int j=0;j<size;j++){path(prev,graph,i,j);}}}static void path(Vertex[][] prev, List<Vertex> graph, int i, int j) {LinkedList<String> stack = new LinkedList<>();System.out.print("[" + graph.get(i).name + "," + graph.get(j).name + "] ");stack.push(graph.get(j).name);while (i != j) {Vertex p = prev[i][j];stack.push(p.name);j = graph.indexOf(p);}System.out.println(stack);}static void print(int[][] dist) {System.out.println("-------------");for (int[] row : dist) {System.out.println(Arrays.stream(row).boxed().map(x -> x == Integer.MAX_VALUE ? "∞" : String.valueOf(x)).map(s -> String.format("%2s", s)).collect(Collectors.joining(",", "[", "]")));}}static void print(Vertex[][] prev) {System.out.println("-------------------------");for (Vertex[] row : prev) {System.out.println(Arrays.stream(row).map(v -> v == null ? "null" : v.name).map(s -> String.format("%5s", s)).collect(Collectors.joining(",", "[", "]")));}}}

Floyd能否判断负环 

        v1    v2    v3    v4

 v1  0       2     ∞       ∞

v2   ∞    0        -4     ∞

v3  1     ∞         0       1

v4  ∞    ∞         ∞        0

k=0

        v1    v2    v3    v4

 v1  0       2     ∞       ∞

v2   ∞    0        -4     ∞

v3  1     3         0       1

v4  ∞    ∞         ∞        0

k=1

        v1    v2    v3    v4

 v1  0       2     -2       -1

v2   ∞    0        -4     ∞

v3  1     3         -1      1

v4  ∞    ∞         ∞        0

......

负环

如果在 3 层循环结束后,在 dist 数组的对角线处(i==j 处)发现了负数,表示出现了负环

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

利用低代码技术,企业怎样开拓数字化转型新路径?

近年来&#xff0c;随着技术的发展和市场竞争的加剧&#xff0c;企业数字化转型已成为一种趋势。许多企业已经完成了线上协作办公的初步转型&#xff0c;这主要得益于像钉钉、企微等发展完善的平台&#xff0c;只需将员工全部拉入这些平台&#xff0c;就能实现线上协作办公。 然…

2024年甘肃省职业院校技能大赛信息安全管理与评估 样题一 模块二

竞赛需要完成三个阶段的任务&#xff0c;分别完成三个模块&#xff0c;总分共计 1000分。三个模块内容和分值分别是&#xff1a; 1.第一阶段&#xff1a;模块一 网络平台搭建与设备安全防护&#xff08;180 分钟&#xff0c;300 分&#xff09;。 2.第二阶段&#xff1a;模块二…

muduo网络库剖析——通道Channel类

muduo网络库剖析——通道Channel类 前情从muduo到my_muduo 概要事件种类channel 框架与细节成员函数细节实现使用方法 源码结尾 前情 从muduo到my_muduo 作为一个宏大的、功能健全的muduo库&#xff0c;考虑的肯定是众多情况是否可以高效满足&#xff1b;而作为学习者&#x…

Linux学习记录——사십삼 高级IO(4)--- Epoll型服务器(1)

文章目录 1、理解Epoll和对应接口2、简单实现 1、理解Epoll和对应接口 poll依然需要OS去遍历所有fd。一个进程去多个特定的文件中等待&#xff0c;只要有一个就绪&#xff0c;就使用select/poll系统调用&#xff0c;让操作系统把所有文件遍历一遍&#xff0c;哪些就绪就加上哪…

07-微服务getaway网关详解

一、初识网关 在微服务架构中&#xff0c;一个系统会被拆分为很多个微服务。那么作为客户端要如何去调用这么多的微服务呢&#xff1f;如果没有网关的存在&#xff0c;我们只能在客户端记录每个微服务的地址&#xff0c;然后分别去调用。这样的话会产生很多问题&#xff0c;例…

Databend 开源周报第 128 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 使用 Databend …

BuildRoot配置RTL8822CE WIFIBT模块(WIFI部分)

TinkerBoard2主板自带的无线模块为RTL8822CE&#xff0c;PCIe接口 之前在风火轮下载的Linux源码编译出来的BuildRoot根文件系统没有相关的驱动文件 [rootrk3399:/]# find . -name *.ko [rootrk3399:/]# lsmod Module Size Used by Not tainted [rootrk33…

UI设计中插画赏析和产品色彩分析

插画赏析&#xff1a; 1. 插画是设计的原创性和艺术性的基础 无论是印刷品、品牌设计还是UI界面&#xff0c;更加风格化的插画能够将不同的风格和创意加入其中&#xff0c;在激烈的竞争中更容易因此脱颖而出。留下用户才有转化。 2. 插画是视觉触发器&#xff0c;瞬间传达大量…

ARM day1

一、概念 ARM可以工作的七种模式用户、系统、快中断、中断、管理、终止、未定义ARM核的寄存器个数 37个32位长的寄存器&#xff0c;当前处理器的模式决定着哪组寄存器可操作&#xff0c;且任何模式都可以存取&#xff1a; PC(program counter程序计数器) CPSR(current program…

自存angular cli创建分区的module

创建module ng g module /admin/promotion --routing 目标文件夹下会有 正常创建组件 在上一级路由中写 promotion的路由 {path: "promotion", //推广loadChildren: () >import("./promotion/promotion.module").then((m) > m.PromotionModul…

详解React与Vue的性能对比

React 和 Vue 是当前最流行的前端开发框架之一。它们都具有高度的灵活性和可扩展性&#xff0c;但在某些方面有所不同。在本篇文章中&#xff0c;我将详细介绍 React 和 Vue 这两个技术&#xff0c;并比较它们的优点和缺点。 目录 1. React&#xff1a; 1.1 优点&#xff1a; …

力扣白嫖日记(sql)

前言 练习sql语句&#xff0c;所有题目来自于力扣&#xff08;https://leetcode.cn/problemset/database/&#xff09;的免费数据库练习题。 今日题目&#xff1a; 586.订单最多的客户 表&#xff1a;Orders 列名类型order_numberintcustomer_numberint 查找下了最多订单的…

QT第五天

使用QT绘图和绘图事件&#xff0c;完成仪表盘绘图&#xff0c;如下图&#xff1a; 程序运行结果&#xff1a; 代码&#xff1a; widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPainter> #include <QPen> #include <QBrush&…

PDF 文档解除密码

PDF 文档解除密码 1. 文件 -> 文档属性 -> 安全 -> 文档限制摘要2. PDF365References 1. 文件 -> 文档属性 -> 安全 -> 文档限制摘要 密码保护《算法设计与分析基础_第3版.pdf》 2. PDF365 https://www.pdf365.cn/ 免费功能 -> PDF 去密码 开始去除 Re…

MySQL入门篇:事物操作(开启事物,提交事物,回滚事物),事物四大特性(ACID),并发事物问题(脏读,不可重复读,幻读),事物隔离级别

目录 1.事物简介2.事物操作1.查看/设置事物提交方式&#xff08;方式1&#xff09;2.开启事物&#xff08;方式2&#xff09;3.提交事物4.回滚事物 3.事物四大特性(ACID)1.原子性&#xff08;Atomicity)2.一致性&#xff08;Consistency)3.隔离性&#xff08;lsolation)4.持久性…

数据结构奇妙旅程之二叉树初阶

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …

腾讯云添加SSL证书

一、进入腾讯云SSL证书&#xff1a; ssl证书控制台地址 选择“我的证书”&#xff0c;点击"申请免费证书" 2、填写域名和邮箱&#xff0c;点击“提交申请” 在此页面中会出现主机记录和记录值。 2、进入云解析 DNS&#xff1a;云解析DNS地址 进入我的解析-记录…

一、MySQL 卸载

目录 1、软件的卸载准备 2、软件的卸载 方式一&#xff1a;通过控制面板卸载 方式二&#xff1a;通过mysql8的安装向导卸载 1、双击mysql8的安装向导 2、取消更新 3、选择要卸载的mysql服务器软件的具体版本 4、确认删除数据目录 5、执行删除 6、完成删除 3、清理残…

verilog编程题

verilog编程题 文章目录 verilog编程题序列检测电路&#xff08;状态机实现&#xff09;分频电路计数器译码器选择器加减器触发器寄存器 序列检测电路&#xff08;状态机实现&#xff09; module Detect_101(input clk,input rst_n,input data,o…

机器人持续学习基准LIBERO系列4——robosuite最基本demo

0.前置 机器人持续学习基准LIBERO系列1——基本介绍与安装测试机器人持续学习基准LIBERO系列2——路径与基准基本信息机器人持续学习基准LIBERO系列3——相机画面可视化及单步移动更新 1.robosuite的相关资料 是基于MuJoCo的机器人学习方针环境&#xff0c;提供一套基准环境…