迪杰斯特拉 (Dijkstra)算法求最短路径问题

简介: 迪杰斯特拉( Dijkstra )算法是典型最短路径算法,用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

目录
算法介绍
应用实例
算法步骤
代码实现
__

算法介绍
迪杰斯特拉( Dijkstra )算法是典型最短路径算法,用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。
应用实例

算法步骤
1)设置出发顶点为 v ,顶点集合 VfvI ,v2, vi .), v 到 V 各顶点的距离构成距离集合 Dis , Dis ( dI ,d2, di .), Dis 集合记录着 v 到图中各顶点的距离(到自身可以看作0, v 到 vi 距离对应为 di )
2)从 Dis 中选择值最小的 di 并移出 Dis 集合,同时移出 V 集合中对应的项点 vi ,此时的 v 到 vi 即为最短路径
3)更新 Dis 集合,更新规则为:比较 v 到 V 集合中顶点的距离值,与 v 通过 vi 到 V 集合中顶点的距离值,保留
值较小的一个(同时也应该更新顶点的前驱节点为 vi ,表明是通过 vi 到达的)
4)重复执行两步骤,直到最短路径顶点为目标顶点即可结束。
代码实现

  1. import java.util.Arrays;
  2. public class _最短路{
  3. static int[] vis;//标记已经访问的顶点 0未访问 1 访问
  4. static int[] dis;//出发顶点到各个下标对应顶点的最短距离
  5. static int[] pre;//每个下标对应的上一个顶点下标
  6. static char[] vertex;//顶点
  7. static int[][] matrix;//邻接矩阵
  8. public static void main(String[] args) {
  9. vertex= new char[]{'A','B','C','D','E','F','G'};
  10. matrix = new intvertex.length;
  11. chushihua(matrix);//初始化邻接矩阵
  12. djstl(vertex.length,6);//调用算法
  13. }
  14. public static void djstl(int length,int start) {
  15. vis=new int[length];
  16. dis=new int[length];
  17. pre=new int[length];
  18. Arrays.fill(dis, 9999);//初始化距离为较大值
  19. dis[start] = 0;//初始化出发顶点到自身的距离0
  20. / 先将起始点到与其连通的顶点的路径及pre前一个顶点进行更新/
  21. update(start);
  22. //在以与起始点相连的顶点为起点 更新距离和路径
  23. for (int i = 1; i < vertex.length; i++) {
  24. int minIndex = -1;
  25. int mindis=9999;
  26. //找到一个最短路径
  27. for (int j = 0; j < vertex.length; j++) {
  28. if(vis[j]==0 && dis[j] < mindis) {
  29. minIndex = j;
  30. mindis = dis[j];
  31. }
  32. }
  33. vis[minIndex] = 1;
  34. update(minIndex);//继续更新
  35. }
  36. System.out.println(Arrays.toString(dis));
  37. }
  38. /**
    • 以index顶点向下查找!!!以起点start到index附近的邻接结点的最短路径!!!
    • @param index
  39. */
  40. public static void update(int index) {
  41. vis[index] = 1;//index标记为已访问
  42. int len= 0;//len:从start顶点到index顶点的距离+上从index再到i顶点的距离
  43. //循环遍历每个邻接结点顶点,找到真正意义上的最短路径
  44. for (int i = 0; i < matrix[index].length; i++) {
  45. //记录从start顶点到index顶点的距离+上从index再到i顶点的距离
  46. len = dis[index] + matrixindex;
  47. //将dis[i] 即从start直接到i 的距离 与len进行比较
  48. if(vis[i] == 0 && len < dis[i]) {
  49. dis[i] = len;//更新最短路径
  50. pre[i] = index;//更新前置顶点
  51. }
  52. }
  53. }
  54. /**
    • 初始化邻接矩阵
    • @param matrix
  55. */
  56. public static void chushihua(int[][] matrix) {
  57. final int N = 9999;
  58. matrix[0]=new int[]{N,5,7,N,N,N,2};
  59. matrix[1]=new int[]{5,N,N,9,N,N,3};
  60. matrix[2]=new int[]{7,N,N,N,8,N,N};
  61. matrix[3]=new int[]{N,9,N,N,N,4,N};
  62. matrix[4]=new int[]{N,N,8,N,N,5,4};
  63. matrix[5]=new int[]{N,N,N,4,5,N,6};
  64. matrix[6]=new int[]{2,3,N,N,4,6,N};
  65. }
  66. }
相关文章
|
3月前
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
73 5
|
14天前
|
算法 机器人 定位技术
基于机器视觉和Dijkstra算法的平面建筑群地图路线规划matlab仿真
本程序基于机器视觉与Dijkstra算法,实现平面建筑群地图的路径规划。通过MATLAB 2022A读取地图图像,识别障碍物并进行路径搜索,支持鼠标选择起点与终点,最终显示最优路径及长度,适用于智能导航与机器人路径规划场景。
|
6月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
157 15
|
7月前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
5月前
|
运维 监控 算法
基于 Python 迪杰斯特拉算法的局域网计算机监控技术探究
信息技术高速演进的当下,局域网计算机监控对于保障企业网络安全、优化资源配置以及提升整体运行效能具有关键意义。通过实时监测网络状态、追踪计算机活动,企业得以及时察觉潜在风险并采取相应举措。在这一复杂的监控体系背后,数据结构与算法发挥着不可或缺的作用。本文将聚焦于迪杰斯特拉(Dijkstra)算法,深入探究其在局域网计算机监控中的应用,并借助 Python 代码示例予以详细阐释。
114 6
|
7月前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
7月前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
13天前
|
机器学习/深度学习 算法 新能源
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
|
15天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的XGBoost时间序列预测算法matlab仿真
本程序基于Matlab 2024b实现,结合粒子群优化(PSO)与XGBoost算法,用于时间序列预测。通过PSO优化XGBoost超参数,提升预测精度。程序包含完整注释与操作视频,运行后生成预测效果图及性能评估指标RMSE。
|
13天前
|
传感器 并行计算 算法
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)
【无人机编队】基于非支配排序遗传算法II NSGA-II高效可行的无人机离线集群仿真研究(Matlab代码实现)

热门文章

最新文章