最短路问题之Dijkstra算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最短路问题之Dijkstra算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4296字，纯文字阅读大概需要7分钟。

内容图文

题目：

　　在上一篇博客的基础上，这是另一种方法求最短路径的问题。

　　Dijkstra（迪杰斯特拉）算法：找到最短距离已经确定的点，从它出发更新相邻顶点的最短距离。此后不再关心前面已经确定的“最短距离已经确定的点”。

　　Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。

　　初始时，集合T只有顶点s。然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

 

代码：

  1 import java.util.HashSet;
  2 import java.util.Set;
  3 
  4 public class 图的最短路问题_Dijkstra {
  5     public static void main(String[] args) {
  6         int s = 1;
  7         int[] shortestPath = shortestPath(s);
  8 
  9         for (int i = 0; i < prev.length; i++) {
 10             System.out.println((char) ('A' + s) + "到" + (char) ('A' + i) + "的路径");
 11             System.out.print((char) ('A' + i) + "<-");
 12             int j = prev[i];
 13             while (j != s) {
 14                 System.out.print((char) ('A' + j) + "<-");
 15                 j = prev[j];
 16             }
 17             System.out.print((char) ('A' + j));
 18             System.out.println(":" + shortestPath[i]);
 19         }
 20     }
 21 
 22     static int[] prev;
 23 
 24     /**
 25      * 求起点到各顶点的最短距离
 26      * 
 27      * @param s 起点
 28      * @return
 29      */
 30     private static int[] shortestPath(int s) {
 31         // 顶点个数
 32         int n = graph.length;
 33         // 记录每个点的前驱
 34         prev = new int[n];
 35         // 一定要初始化，源点的前驱是自身
 36         prev[s] = s;
 37         // 记录s到各顶点的最短距离
 38         int[] d = new int[n];
 39         d[s] = 0;// 自己到自己的距离为0
 40         // 记录已经找到最短距离的顶点
 41         Set<Integer> T = new HashSet<>();
 42         T.add(s);
 43 
 44         /*-第一步：直接可达的顶点，用距离来初始化d,d[s]=0，可直达的把距离记录下来作为待定值-*/
 45         for (int i = 0; i < n; i++) {
 46             if (i != s && graph[s][i] == 0)
 47                 d[i] = Integer.MAX_VALUE;// 不可直达的顶点，先以最大整数作为待定值
 48             if (i != s && graph[s][i] > 0) {
 49                 d[i] = graph[s][i]; // 可直达的顶点，以直达距离作为待定值
 50                 prev[i] = s; // 可直达的顶点，其前驱是源点
 51             }
 52         }
 53         // Util.print(d);
 54 
 55         while (T.size() < n) {
 56             /*-第二步：从待定的距离表中找到最小值，这个值可以作为确定值，为什么？-*/
 57             int min = minIndex(d, T);
 58             T.add(min);
 59             if (T.size() == n)
 60                 break;
 61             /*-第三步，看这个新确定的顶点的出度，看看从源点出发是经过这个顶点到其邻居近还是直达更近,如果更近就要更新-*/
 62             // 扫描index的邻居
 63             for (int neighbor = 0; neighbor < n; neighbor++) {
 64                 int cost = graph[min][neighbor];
 65                 // 更新
 66                 if (cost > 0 && d[neighbor] > d[min] + cost) {
 67                     d[neighbor] = d[min] + cost;
 68                     prev[neighbor] = min; // 更新最短路后，要更新i这个点的前驱
 69                 }
 70             }
 71         }
 72         return d;
 73     }
 74 
 75     /**
 76      * 从未确定的点里面找一个最小的
 77      * 
 78      * @param d
 79      * @param t 已确定了最短距离的顶点集
 80      * @return
 81      */
 82     private static int minIndex(int[] d, Set<Integer> t) {
 83         int index = -1;
 84         int min = Integer.MAX_VALUE;
 85         for (int i = 0; i < d.length; i++) {
 86             if (!t.contains(i) && d[i] < min) {
 87                 min = d[i];
 88                 index = i;
 89             }
 90         }
 91         return index;
 92     }
 93 
 94     static int[][] graph = { 
 95             { 0, 2, 5, 0, 0, 0, 0 }, 
 96             { 2, 0, 4, 6, 10, 0, 0 }, 
 97             { 5, 4, 0, 2, 0, 0, 0 },
 98             { 0, 6, 2, 0, 0, 1, 0 }, 
 99             { 0, 10, 0, 0, 0, 3, 5 }, 
100             { 0, 0, 0, 1, 3, 0, 9 }, 
101             { 0, 0, 0, 0, 5, 9, 0 } 
102             };
103 }

结果：

　　

 

内容总结

以上是互联网集市为您收集整理的最短路问题之Dijkstra算法全部内容，希望文章能够帮你解决最短路问题之Dijkstra算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---