【数据结构-图】最短路径

news/2025/2/16 5:29:22/

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

    • 一.Dijkstra
      • 1.Dijkstra 简介
      • 2.有向无环图
      • 3.算法描述
      • 4.java 实现
      • 5.优化改进
      • 6.存在问题
    • 二.Bellman-Ford
      • 1.java 实现
      • 2.负环
    • 三.Floyd-Warshall
      • 1.负环图
      • 2.java 实现
      • 3.负环

一.Dijkstra

1.Dijkstra 简介

image-20230925193327109

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 分布式计算有影响力论文奖。为了纪念他，该年度奖项在接下来的一年更名为迪克斯特拉奖。

迪克斯特拉在计算机科学领域的贡献

  1. 最短路径算法，也称为迪克斯特拉算法，现代计算机科学本科课程中广泛教授
  2. Shunting yard 算法
  3. THE OS 操作系统
  4. 银行家算法
  5. 用于协调多个处理器和程序的信号量构造
  6. 在分布式计算领域提出概念：自稳定性

2.有向无环图

7
9
14
9
2
15
11
6
1
2
3
4
5
6

3.算法描述

算法描述：

  1. 将所有顶点标记为未访问。创建一个未访问顶点的集合。
  2. 为每个顶点分配一个临时距离值
    • 对于我们的初始顶点，将其设置为零
    • 对于所有其他顶点，将其设置为无穷大。
  3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点
  4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
    • 例如，1->6 的距离是 14，而 1->3->6 的距离是 11。这时将距离更新为 11
    • 否则，将保留上次距离值
  5. 当前顶点的邻居处理完成后，把它从未访问集合中删除

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));List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(List<Vertex> graph, Vertex source) {ArrayList<Vertex> 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, ArrayList<Vertex> 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(ArrayList<Vertex> 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. 创建一个优先级队列，放入所有顶点（队列大小会达到边的数量）
  2. 为每个顶点分配一个临时距离值
    • 对于我们的初始顶点，将其设置为零
    • 对于所有其他顶点，将其设置为无穷大。
  3. 每次选择最小临时距离的未访问顶点，作为新的当前顶点
  4. 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小，若距离更新需加入队列
    • 例如，1->6 的距离是 14，而 1->3->6 的距离是 11。这时将距离更新为 11
    • 否则，将保留上次距离值
  5. 当前顶点的邻居处理完成后，把它从队列中删除
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));List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);dijkstra(graph, v1);}private static void dijkstra(List<Vertex> graph, Vertex source) {PriorityQueue<Vertex> 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, PriorityQueue<Vertex> 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.存在问题

有负数边的情况

2
1
-2
1
v1
v2
v3
v4

按照 Dijkstra 算法，得出

  • v1 -> v2 最短距离 2
  • v1 -> v3 最短距离 1
  • v1 -> v4 最短距离 2

事实应当是

  • v1 -> v2 最短距离 2
  • v1 -> v3 最短距离 0
  • v1 -> 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));List<Vertex> 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();List<Vertex> 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();List<Vertex> graph = List.of(v1, v2, v3, v4);bellmanFord(graph, v1);}private static void bellmanFord(List<Vertex> 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.负环

2
-4
1
1
v1
v2
v3
v4

如果在【顶点-1】轮处理完成后，还能继续找到更短距离，表示发现了负环

三.Floyd-Warshall

1.负环图

-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));List<Vertex> graph = List.of(v1, v2, v3, v4);/*直接连通v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   3   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0k=0 借助v1到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  ∞   -1  ∞   0k=1 借助v2到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  ∞v2  4   0   2   ∞v3  ∞   ∞   0   2v4  3   -1  1   0k=2 借助v3到达其它顶点v1  v2  v3  v4v1  0   ∞   -2  0v2  4   0   2   4v3  ∞   ∞   0   2v4  3   -1  1   0k=3 借助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); // 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, 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(",", "[", "]")));}}}

3.负环

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

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙

img


http://www.ppmy.cn/news/1125458.html

相关文章

AI编程助手 Amazon CodeWhisperer 全面解析与实践

AI编程助手 Amazon CodeWhisperer 全面解析与实践

目录 引言Amazon CodeWhisperer简介智能编程助手智能代码建议代码自动补全 提升代码质量代码质量提升安全性检测 支持多平台多语言 用户体验和系统兼容性用户体验文档和学习资源个性化体验系统兼容性 功能全面性和代码质量功能全面性代码生成质量和代码安全性 CodeWhisperer的代…
阅读更多...
[动物文学]走红年轻人化身“精神动物”，这届年轻人不想做人了

[动物文学]走红年轻人化身“精神动物”，这届年轻人不想做人了

数据洞察流行趋势&#xff0c;敏锐把握流量风口。本期千瓜与您分享近期小红书八大热点内容&#xff0c;带您看热点、追热门、借热势&#xff0c;为您提供小红书营销布局风向标。 「动物文学」走红 年轻人化身“精神动物” 其实&#xff0c;这届年轻人“不想做人”很久了………
阅读更多...
腾讯云微服务平台 TSF 异地多活单元化能力重磅升级

腾讯云微服务平台 TSF 异地多活单元化能力重磅升级

导语 2023腾讯全球数字生态大会已于9月7-8日完美落幕&#xff0c;40专场活动展示了腾讯最新的前沿技术、核心产品、解决方案。 微服务与消息队列专场&#xff0c;腾讯云微服务平台 TSF 产品经理张桢带来了《腾讯云微服务平台 TSF 异地多活单元化能力重磅升级》的精彩演讲。本…
阅读更多...
ShapeableImageView 不只是圆形ImageView

ShapeableImageView 不只是圆形ImageView

偶然间看到了这位老哥的 https://juejin.cn/post/6869376452040196109#comment 文章&#xff0c;发现了ShapeableImageView–一个多形状的ImageView &#xff0c;虽然似乎发布了很久了&#xff0c;现在学习不晚。 效果图 布局文件 <com.google.android.material.imageview.S…
阅读更多...
rust学习-string

rust学习-string

介绍 A UTF-8–encoded, growable string（可增长字符串）. 拥有string内容的所有权 A String is made up of three components: a pointer to some bytes, a length, and a capacity. The length is the number of bytes currently stored in the buffer pub fn as_bytes(&…
阅读更多...
【Linux】C语言实现对文件的加密算法

【Linux】C语言实现对文件的加密算法

异或加密 解密方式是进行第二次加密后自动解密 #define BUF_SIZE (16384) //16k /************************************************************** 功能描述: 加密实现 输入参数: --------------------------------------------------------------- 修改作者: 修改日期…
阅读更多...
Java SE 21 新增特性

Java SE 21 新增特性

Java SE 21 新增特性 作者&#xff1a;Grey 原文地址&#xff1a; 博客园&#xff1a;Java SE 21 新增特性 CSDN&#xff1a;Java SE 21 新增特性 源码 源仓库: Github&#xff1a;java_new_features 镜像仓库: GitCode&#xff1a;java_new_features Record Patterns …
阅读更多...
PDAF简介

PDAF简介

自动对焦系统 Laser AF Laser AF (Laser Auto Focus&#xff0c;激光对焦) 通过发射红外线感知物体的距离&#xff0c;根据距离事先校准好一组距离与Focus Distance的对应mapping关系。优缺点&#xff1a;受环境因素影响较大&#xff0c;成本高。 CDAF CDAF (Contrast De…
阅读更多...
最新文章

Copyright @ 2022~2023