竹子建站公司,怎么在百度上创建自己的网页,网站设计亮点,贸易网站设计公司#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 博客目录 一.Dijkstra1.Dijkstra 简介2.有向无环图3.算法描述4.java 实现5.优化改进6.存在问题 二.Bellman-Ford1.java 实现2.负环 三.Floyd-Warshall1.负环图2.java 实现3.负环 一.Dijkstra
1.Dijkstra 简介 Edsger Wybe Dijkstra 艾兹格·维布·迪克斯特拉Edsger Wybe Dijkstra/ˈdaɪkstrə/ DYKE-strə荷兰语[ˈɛtsxər ˈʋibə ˈdɛikstra] 1930 年 5 月 11 日-2002 年 8 月 6 日是一位荷兰计算机科学家、程序员、软件工程师、系统科学家和科学散文家。他因对开发结构化编程语言做出的基础贡献而获得了 1972 年的图灵奖并担任德克萨斯大学奥斯汀分校的斯伦贝谢百年计算机科学主席任职时间从 1984 年到 2000 年。在他于 2002 年去世前不久他因其在程序计算的自稳定性方面的工作而获得了 ACM PODC 分布式计算有影响力论文奖。为了纪念他该年度奖项在接下来的一年更名为迪克斯特拉奖。 迪克斯特拉在计算机科学领域的贡献 最短路径算法也称为迪克斯特拉算法现代计算机科学本科课程中广泛教授Shunting yard 算法THE OS 操作系统银行家算法用于协调多个处理器和程序的信号量构造在分布式计算领域提出概念自稳定性 2.有向无环图 #mermaid-svg-OXI9b3J8ukLw0Mu6 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .error-icon{fill:#552222;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .marker.cross{stroke:#333333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .cluster-label text{fill:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .cluster-label span{color:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .label text,#mermaid-svg-OXI9b3J8ukLw0Mu6 span{fill:#333;color:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .node rect,#mermaid-svg-OXI9b3J8ukLw0Mu6 .node circle,#mermaid-svg-OXI9b3J8ukLw0Mu6 .node ellipse,#mermaid-svg-OXI9b3J8ukLw0Mu6 .node polygon,#mermaid-svg-OXI9b3J8ukLw0Mu6 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .node .label{text-align:center;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .node.clickable{cursor:pointer;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .arrowheadPath{fill:#333333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .cluster text{fill:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 .cluster span{color:#333;}#mermaid-svg-OXI9b3J8ukLw0Mu6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-OXI9b3J8ukLw0Mu6 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 7 9 14 9 2 15 11 6 1 2 3 4 5 6 3.算法描述
算法描述
将所有顶点标记为未访问。创建一个未访问顶点的集合。为每个顶点分配一个临时距离值 对于我们的初始顶点将其设置为零对于所有其他顶点将其设置为无穷大。 每次选择最小临时距离的未访问顶点作为新的当前顶点对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小 例如1-6 的距离是 14而 1-3-6 的距离是 11。这时将距离更新为 11否则将保留上次距离值 当前顶点的邻居处理完成后把它从未访问集合中删除
4.java 实现
public class Dijkstra {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);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));v2.edges List.of(new Edge(v4, 15));v3.edges List.of(new Edge(v4, 11), new Edge(v6, 2));v4.edges List.of(new Edge(v5, 6));v5.edges List.of();v6.edges List.of(new Edge(v5, 9));ListVertex graph List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(ListVertex graph, Vertex source) {ArrayListVertex list new ArrayList(graph);source.dist 0;while (!list.isEmpty()) {// 3. 选取当前顶点Vertex curr chooseMinDistVertex(list);// 4. 更新当前顶点邻居距离updateNeighboursDist(curr, list);// 5. 移除当前顶点list.remove(curr);}for (Vertex v : graph) {System.out.println(v.name v.dist);}}private static void updateNeighboursDist(Vertex curr, ArrayListVertex list) {for (Edge edge : curr.edges) {Vertex n edge.linked;if (list.contains(n)) {int dist curr.dist edge.weight;if (dist n.dist) {n.dist dist;}}}}private static Vertex chooseMinDistVertex(ArrayListVertex list) {Vertex min list.get(0);for (int i 1; i list.size(); i) {if (list.get(i).dist min.dist) {min list.get(i);}}return min;}}5.优化改进
改进 - 优先级队列
创建一个优先级队列放入所有顶点队列大小会达到边的数量为每个顶点分配一个临时距离值 对于我们的初始顶点将其设置为零对于所有其他顶点将其设置为无穷大。 每次选择最小临时距离的未访问顶点作为新的当前顶点对于当前顶点遍历其所有未访问的邻居并更新它们的临时距离为更小若距离更新需加入队列 例如1-6 的距离是 14而 1-3-6 的距离是 11。这时将距离更新为 11否则将保留上次距离值 当前顶点的邻居处理完成后把它从队列中删除
public class DijkstraPriorityQueue {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);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));v2.edges List.of(new Edge(v4, 15));v3.edges List.of(new Edge(v4, 11), new Edge(v6, 2));v4.edges List.of(new Edge(v5, 6));v5.edges List.of();v6.edges List.of(new Edge(v5, 9));ListVertex graph List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(ListVertex graph, Vertex source) {PriorityQueueVertex queue new PriorityQueue(Comparator.comparingInt(v - v.dist));source.dist 0;for (Vertex v : graph) {queue.offer(v);}while (!queue.isEmpty()) {System.out.println(queue);// 3. 选取当前顶点Vertex curr queue.peek();// 4. 更新当前顶点邻居距离if(!curr.visited) {updateNeighboursDist(curr, queue);curr.visited true;}// 5. 移除当前顶点queue.poll();}for (Vertex v : graph) {System.out.println(v.name v.dist (v.prev ! null ? v.prev.name : null));}}private static void updateNeighboursDist(Vertex curr, PriorityQueueVertex queue) {for (Edge edge : curr.edges) {Vertex n edge.linked;if (!n.visited) {int dist curr.dist edge.weight;if (dist n.dist) {n.dist dist;n.prev curr;queue.offer(n);}}}}}6.存在问题
有负数边的情况 #mermaid-svg-DOl3jF8DU9AEaRQr {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr .error-icon{fill:#552222;}#mermaid-svg-DOl3jF8DU9AEaRQr .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-DOl3jF8DU9AEaRQr .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-DOl3jF8DU9AEaRQr .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-DOl3jF8DU9AEaRQr .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-DOl3jF8DU9AEaRQr .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-DOl3jF8DU9AEaRQr .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-DOl3jF8DU9AEaRQr .marker{fill:#333333;stroke:#333333;}#mermaid-svg-DOl3jF8DU9AEaRQr .marker.cross{stroke:#333333;}#mermaid-svg-DOl3jF8DU9AEaRQr svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-DOl3jF8DU9AEaRQr .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr .cluster-label text{fill:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr .cluster-label span{color:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr .label text,#mermaid-svg-DOl3jF8DU9AEaRQr span{fill:#333;color:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr .node rect,#mermaid-svg-DOl3jF8DU9AEaRQr .node circle,#mermaid-svg-DOl3jF8DU9AEaRQr .node ellipse,#mermaid-svg-DOl3jF8DU9AEaRQr .node polygon,#mermaid-svg-DOl3jF8DU9AEaRQr .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-DOl3jF8DU9AEaRQr .node .label{text-align:center;}#mermaid-svg-DOl3jF8DU9AEaRQr .node.clickable{cursor:pointer;}#mermaid-svg-DOl3jF8DU9AEaRQr .arrowheadPath{fill:#333333;}#mermaid-svg-DOl3jF8DU9AEaRQr .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-DOl3jF8DU9AEaRQr .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-DOl3jF8DU9AEaRQr .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-DOl3jF8DU9AEaRQr .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-DOl3jF8DU9AEaRQr .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-DOl3jF8DU9AEaRQr .cluster text{fill:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr .cluster span{color:#333;}#mermaid-svg-DOl3jF8DU9AEaRQr div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-DOl3jF8DU9AEaRQr :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 2 1 -2 1 v1 v2 v3 v4 按照 Dijkstra 算法得出
v1 - v2 最短距离 2v1 - v3 最短距离 1v1 - v4 最短距离 2
事实应当是
v1 - v2 最短距离 2v1 - v3 最短距离 0v1 - v4 最短距离 1
二.Bellman-Ford
1.java 实现
public class BellmanFord {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);Vertex v5 new Vertex(v5);Vertex v6 new Vertex(v6);v1.edges List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));v2.edges List.of(new Edge(v4, 15));v3.edges List.of(new Edge(v4, 11), new Edge(v6, 2));v4.edges List.of(new Edge(v5, 6));v5.edges List.of();v6.edges List.of(new Edge(v5, 9));ListVertex graph List.of(v4, v5, v6, v1, v2, v3);*/// 负边情况/*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(v2, 2), new Edge(v3, 1));v2.edges List.of(new Edge(v3, -2));v3.edges List.of(new Edge(v4, 1));v4.edges List.of();ListVertex graph List.of(v1, v2, v3, v4);*/// 负环情况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(v2, 2));v2.edges List.of(new Edge(v3, -4));v3.edges List.of(new Edge(v4, 1), new Edge(v1, 1));v4.edges List.of();ListVertex graph List.of(v1, v2, v3, v4);bellmanFord(graph, v1);}private static void bellmanFord(ListVertex graph, Vertex source) {source.dist 0;int size graph.size();// 1. 进行 顶点个数 - 1 轮处理for (int i 0; i size - 1; i) {// 2. 遍历所有的边for (Vertex s : graph) {for (Edge edge : s.edges) {// 3. 处理每一条边Vertex e edge.linked;if (s.dist ! Integer.MAX_VALUE s.dist edge.weight e.dist) {e.dist s.dist edge.weight;e.prev s;}}}}for (Vertex v : graph) {System.out.println(v (v.prev ! null ? v.prev.name : null));}}
}2.负环 #mermaid-svg-DJyQJcjmi2XIeVvN {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN .error-icon{fill:#552222;}#mermaid-svg-DJyQJcjmi2XIeVvN .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-DJyQJcjmi2XIeVvN .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-DJyQJcjmi2XIeVvN .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-DJyQJcjmi2XIeVvN .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-DJyQJcjmi2XIeVvN .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-DJyQJcjmi2XIeVvN .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-DJyQJcjmi2XIeVvN .marker{fill:#333333;stroke:#333333;}#mermaid-svg-DJyQJcjmi2XIeVvN .marker.cross{stroke:#333333;}#mermaid-svg-DJyQJcjmi2XIeVvN svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-DJyQJcjmi2XIeVvN .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN .cluster-label text{fill:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN .cluster-label span{color:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN .label text,#mermaid-svg-DJyQJcjmi2XIeVvN span{fill:#333;color:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN .node rect,#mermaid-svg-DJyQJcjmi2XIeVvN .node circle,#mermaid-svg-DJyQJcjmi2XIeVvN .node ellipse,#mermaid-svg-DJyQJcjmi2XIeVvN .node polygon,#mermaid-svg-DJyQJcjmi2XIeVvN .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-DJyQJcjmi2XIeVvN .node .label{text-align:center;}#mermaid-svg-DJyQJcjmi2XIeVvN .node.clickable{cursor:pointer;}#mermaid-svg-DJyQJcjmi2XIeVvN .arrowheadPath{fill:#333333;}#mermaid-svg-DJyQJcjmi2XIeVvN .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-DJyQJcjmi2XIeVvN .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-DJyQJcjmi2XIeVvN .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-DJyQJcjmi2XIeVvN .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-DJyQJcjmi2XIeVvN .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-DJyQJcjmi2XIeVvN .cluster text{fill:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN .cluster span{color:#333;}#mermaid-svg-DJyQJcjmi2XIeVvN div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-DJyQJcjmi2XIeVvN :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 2 -4 1 1 v1 v2 v3 v4 如果在【顶点-1】轮处理完成后还能继续找到更短距离表示发现了负环
三.Floyd-Warshall
1.负环图 #mermaid-svg-olsLeK8R4GoaR1CD {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-olsLeK8R4GoaR1CD .error-icon{fill:#552222;}#mermaid-svg-olsLeK8R4GoaR1CD .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-olsLeK8R4GoaR1CD .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-olsLeK8R4GoaR1CD .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-olsLeK8R4GoaR1CD .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-olsLeK8R4GoaR1CD .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-olsLeK8R4GoaR1CD .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-olsLeK8R4GoaR1CD .marker{fill:#333333;stroke:#333333;}#mermaid-svg-olsLeK8R4GoaR1CD .marker.cross{stroke:#333333;}#mermaid-svg-olsLeK8R4GoaR1CD svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-olsLeK8R4GoaR1CD .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-olsLeK8R4GoaR1CD .cluster-label text{fill:#333;}#mermaid-svg-olsLeK8R4GoaR1CD .cluster-label span{color:#333;}#mermaid-svg-olsLeK8R4GoaR1CD .label text,#mermaid-svg-olsLeK8R4GoaR1CD span{fill:#333;color:#333;}#mermaid-svg-olsLeK8R4GoaR1CD .node rect,#mermaid-svg-olsLeK8R4GoaR1CD .node circle,#mermaid-svg-olsLeK8R4GoaR1CD .node ellipse,#mermaid-svg-olsLeK8R4GoaR1CD .node polygon,#mermaid-svg-olsLeK8R4GoaR1CD .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-olsLeK8R4GoaR1CD .node .label{text-align:center;}#mermaid-svg-olsLeK8R4GoaR1CD .node.clickable{cursor:pointer;}#mermaid-svg-olsLeK8R4GoaR1CD .arrowheadPath{fill:#333333;}#mermaid-svg-olsLeK8R4GoaR1CD .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-olsLeK8R4GoaR1CD .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-olsLeK8R4GoaR1CD .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-olsLeK8R4GoaR1CD .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-olsLeK8R4GoaR1CD .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-olsLeK8R4GoaR1CD .cluster text{fill:#333;}#mermaid-svg-olsLeK8R4GoaR1CD .cluster span{color:#333;}#mermaid-svg-olsLeK8R4GoaR1CD div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-olsLeK8R4GoaR1CD :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} -2 4 3 2 -1 v1 v3 v2 v4 2.java 实现
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));ListVertex graph List.of(v1, v2, v3, v4);/*直接连通v1 v2 v3 v4v1 0 ∞ -2 ∞v2 4 0 3 ∞v3 ∞ ∞ 0 2v4 ∞ -1 ∞ 0k0 借助v1到达其它顶点v1 v2 v3 v4v1 0 ∞ -2 ∞v2 4 0 2 ∞v3 ∞ ∞ 0 2v4 ∞ -1 ∞ 0k1 借助v2到达其它顶点v1 v2 v3 v4v1 0 ∞ -2 ∞v2 4 0 2 ∞v3 ∞ ∞ 0 2v4 3 -1 1 0k2 借助v3到达其它顶点v1 v2 v3 v4v1 0 ∞ -2 0v2 4 0 2 4v3 ∞ ∞ 0 2v4 3 -1 1 0k3 借助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(ListVertex 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)MapVertex, 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); // v3if (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);}static void path(Vertex[][] prev, ListVertex graph, int i, int j) {LinkedListString 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(,, [, ])));}}}3.负环
如果在 3 层循环结束后在 dist 数组的对角线处ij 处发现了负数表示出现了负环 觉得有用的话点个赞 呗。 ❤️❤️❤️本人水平有限如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢! Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧
