迪杰斯特拉算法 Dijkstra‘s Algorithm 详解

embedded/2024/12/22 11:02:20/

迪杰斯特拉算法

迪杰斯特拉算法(Dijkstra’s Algorithm)是一个经典的图论算法,用于在带权图中寻找单源最短路径问题。该算法由荷兰计算机科学家艾兹赫尔·迪杰斯特拉于1956年提出,因其高效性和可靠性而广泛应用于网络路由、地理信息系统等领域。本文将详细介绍迪杰斯特拉算法的原理,并提供Java代码实现。

算法原理

迪杰斯特拉算法的基本思想是贪心策略,它维护两个集合:已确定最短路径的顶点集合 S S S和未确定最短路径的顶点集合 U U U算法从起点开始,逐步将 U U U中的顶点按照最短路径长度加入到 S S S中,直到 S S S包含所有顶点。具体步骤如下:

  • 初始化:设置起点 v 0 v_0 v0的距离为0,其余顶点的距离为无穷大。将所有顶点加入 U U U集合。
  • 选择:从 U U U中选择距离起点最小的顶点 u u u,将其从 U U U中移除并加入 S S S
  • 更新:对于 u u u的每个邻接点 v v v,如果通过 u u u到达 v v v的距离比已知的 v v v的距离更短,则更新 v v v的距离。
  • 重复:重复步骤2和3,直到 U U U为空或 S S S包含所有顶点。

Java实现

下面是一个使用Java实现的迪杰斯特拉算法示例代码。这里使用邻接矩阵来表示图。

java">public class Dijkstra {public static final int MAX = Integer.MAX_VALUE; // 表示无穷大public static int[] dijkstra(int[][] graph, int start) {int n = graph.length; // 顶点数量int[] dist = new int[n]; // 存储起点到各顶点的最短距离boolean[] visited = new boolean[n]; // 标记顶点是否已访问// 初始化距离数组for (int i = 0; i < n; i++) {dist[i] = (i == start) ? 0 : MAX;}// 主循环,直到所有顶点都被访问for (int i = 0; i < n; i++) {int minDist = MAX;int u = -1; // 当前最近顶点// 选择未访问顶点中距离最小的顶点for (int j = 0; j < n; j++) {if (!visited[j] && dist[j] < minDist) {minDist = dist[j];u = j;}}if (u == -1) {break; // 所有顶点都已访问}visited[u] = true; // 标记当前顶点已访问// 更新邻接顶点的距离for (int v = 0; v < n; v++) {if (graph[u][v] != 0 && graph[u][v] + minDist < dist[v]) {dist[v] = graph[u][v] + minDist;}}}return dist; // 返回起点到各顶点的最短距离数组}public static void main(String[] args) {// 示例图int[][] graph = {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};int start = 0; // 起始顶点int[] distances = dijkstra(graph, start); // 计算最短距离// 输出结果for (int i = 0; i < distances.length; i++) {if (distances[i] == MAX) {System.out.println("从 " + start + " 到 " + i + " 没有路径");} else {System.out.println("从 " + start + " 到 " + i + " 的最短距离为 " + distances[i]);}}}
}

在上面的代码中,dijkstra方法接收一个表示图的邻接矩阵和起始顶点索引,返回一个整数数组,表示从起始顶点到所有其他顶点的最短距离。MAX常量用于表示无穷大,即两个顶点之间没有直接边相连的情况。

总结

迪杰斯特拉算法是一个简单而强大的算法,用于解决单源最短路径问题。本文介绍了该算法的基本原理,并提供了一个Java实现示例。使用迪杰斯特拉算法时需要注意,该算法不适用于带负权边的图,因为在负权边存在的情况下,最短路径可能不存在或需要更复杂的算法(如贝尔曼-福德算法)来解决。

全文完!


http://www.ppmy.cn/embedded/123395.html

相关文章

《Windows PE》4.1.3 IAT函数地址表

IAT&#xff08;Import Address Table&#xff09;表又称为函数地址表&#xff0c;是Windows可执行文件中的一个重要数据结构&#xff0c;用于存储导入函数的实际入口地址。 在可执行文件中&#xff0c;当一个模块需要调用另一个模块中的函数时&#xff0c;通常会使用导入函数…

Redis中GEO数据结构实现附近商户搜索

Redis的版本必须是6.2以上 在测试类中将数据导入Redis Testvoid loadShopData(){//1.查询店铺信息List<Shop> list shopService.list();//2.把店铺分组&#xff0c;按照typeId分组&#xff0c;typeId一致的放到一个集合Map<Long, List<Shop>> map list.s…

AS-REP Roasting 实验

1. 实验网络拓扑 kali: 192.168.72.128win2008: 192.168.135.129 192.168.72.139win7: 192.168.72.149win2012:(DC) 192.168.72.131 2. 攻击原理 如果设置了不需要Kerberos预认证&#xff1a; 那么就可以直接发AS_REQ请求TGT票据&#xff0c;由于不要求预身份认证&#xff0…

vue-cli老项目继续优化:json压缩神器 compress-json

前言 上文讲到一个 vue-cli 带脚本生成内容的老项目的打包时间已经从 40min &#xff0c;优化到 12min &#xff0c;再到 9min 。 还有可以考虑的方式包含缩小脚本体积、依赖分包、构建的缓存等等。 那么本文就来讨论缩小脚本体积的方式。 分析 前文已知&#xff0c;生成的…

P1088 [NOIP2004 普及组] 火星人

思路就是 全排列中找到题目所给的组合 然后加上的最小数就是往后面数几个组合 就是要求的那个排列 然后输出 我写的那一份代码ac了两个点 其他 全部tle 估计是比较的时间复杂度太高了暴力写法的时间复杂度比内置函数要大很多 暴力208ms 内置31ms 暴力 #include<bits/std…

关于Elastic Search与MySQL之间的数据同步

目录 前言 思路分析 同步调用 异步通知 监听binlog 选择 实现数据同步 思路 运行项目 声明交换机、队列 1&#xff09;引入依赖 2&#xff09;声明队列交换机名称 3&#xff09;声明队列交换机 发送MQ消息 接收MQ消息 前言 Elastic Search中的酒店数据来自于MyS…

工具方法 - 面试中回答问题的技巧

在面试中&#xff0c;回答问题的技巧尤为重要。它不仅展示了你的知识和能力&#xff0c;还体现了你处理压力和沟通的技巧。以下是一些在面试中常用的回答技巧&#xff0c;以及如何在这些场合有效地回应问题的示例&#xff1a; 1. 抓住问题的核心 面试官通常会提出直接的问题&a…

unity3D雨雪等粒子特效不穿透房屋效果实现(粒子不穿透模型)

做项目有时候会做天气模拟&#xff0c;模拟雨雪天气等等。但是容易忽略一个问题&#xff0c;就是房屋内不应该下雨或者下雪&#xff0c;这样不就穿帮了嘛。 下面就粒子穿透物体问题做一个demo。 正常下雨下雪在室内的话&#xff0c;你可以看到&#xff0c;粒子是穿透建筑的。…