Dijkstra算法的Java实现

  1 package main.java;
  2 
  3 import main.java.utils.graphutil;
  4 
  5 import java.util.arraydeque;
  6 import java.util.list;
  7 import java.util.queue;
  8 
  9 
 10 /**
 11  * @tme 2019/9/12 10:40
 12  * @author chenhaisheng
 13  * @email:[e-mail]
 14  */
 15 public class dijkstratest {
 16 
 17     //邻接矩阵的表示
 18     public final static double[][] graph_distance = graphutil.getdijkstragraph();
 19 
 20     //起点到某节点的临时最短距离
 21     public static double distance[] = new double[graph_distance.length];
 22 
 23     //某节点的前驱节点
 24     public static int pre[] = new int[graph_distance.length];
 25 
 26     static int originindex = 0, toindex = 4;
 27 
 28 
 29     public static void main(string[] args) {
 30 
 31         init();
 32         finddijkstrashortestpath();
 33     }
 34 
 35     /*
 36     **初始化distance[]   pre[]
 37      */
 38     public static void init() {
 39 
 40         for (int i = 0; i < distance.length; i++) {
 41             if (i == originindex) {
 42                 distance[i] = 0.0;
 43                 continue;
 44             }
 45             distance[i] = double.max_value;
 46         }
 47 
 48         for (int i = 0; i < pre.length; i++) {
 49             pre[i] = -1;
 50         }
 51     }
 52 
 53     public static void finddijkstrashortestpath() {
 54 
 55         //queue用于保存尚待搜索的节点
 56         queue<integer> queue = new arraydeque<>();
 57 
 58         //起始，将起始节点添加到queue
 59         queue.add(originindex);
 60 
 61         while (queue.size() != 0) {
 62 
 63             integer currentindex = queue.poll();
 64 
 65             //获取当前节点的out-edges
 66             list<integer> neighbours = getneighbours(currentindex);
 67 
 68             for (int i = 0; i < neighbours.size(); i++) {
 69 
 70                 //获取邻居节点的索引值
 71                 int neighbourindex = neighbours.get(i);
 72 
 73                 //若起点经当前节点到邻居节点的距离 比直接到邻居节点的距离还小
 74                 if (distance[currentindex] + getdistance(currentindex, neighbourindex) < distance[neighbourindex]) {
 75 
 76                     //更新起点到邻居节点的距离
 77                     distance[neighbourindex] = distance[currentindex] + getdistance(currentindex, neighbourindex);
 78 
 79                     //设置下一个节点的前驱节点为当前节点
 80                     pre[neighbourindex] = currentindex;
 81 
 82                     //由于distance[neighbourindex]已经改变，因此需要重新搜索neighbourindex
 83                     queue.add(neighbourindex);
 84                 }
 85             }
 86         }
 87 
 88         //输出从originindex到toindex的路径
 89         printpath(pre, originindex, toindex);
 90     }
 91 
 92 
 93     public static void printpath(int pre[], int from, int to) {
 94 
 95         //栈
 96         deque<integer> path = new arraydeque<>();
 97 
 98         path.push(to);
 99 
100         int preindex = pre[to];
101         while (preindex != from) {
102             path.push(preindex);
103             preindex = pre[preindex];
104         }
105 
106         path.push(from);
107 
108         while (!path.isempty()) {
109             system.out.print(path.poll() + (path.size() > 0 ? "------>" : " "));
110         }
111         system.out.println(" ");
112     }
113 
114 
115     //获取当前节点所有的out-edges
116     public static list getneighbours(int index) {
117 
118         list<integer> res = new arraylist();
119 
120         //距离不为double.max_value,代表与当前节点连通
121         for (int i = 0; i < graph_distance[index].length; i++) {
122             if (graph_distance[index][i] != double.max_value)
123                 res.add(i);
124         }
125         return res;
126     }
127 
128     public static double getdistance(int from, int to) {
129         return graph_distance[from][to];
130     }
131 }

 

 1 package main.java.utils;
 2 
 3 /**
 4  * @tme ${data} 19:10
 5  * @author chenhaisheng
 6  * @email:[e-mail]
 7  */
 8 public class graphutil<t> {
 9 
10     public static double[][] getdijkstragraph(){
11         double max=double.max_value;
12         double[][] graph={
13                 {max,5,max,7,15},
14                 {max,max,5,max,max},
15                 {max,max,max,max,1},
16                 {max,max,2,max,max},
17                 {max,max,max,max,max}
18         };
19         return  graph;
20     }
21 }

 

对应的图：

图的结构ref：

 

小结：

最重要的是记住：在搜索过程中，若节点i对应的distance[i]发生改变，那么对其任意一个邻居节点j，对应的distance[j]都要重新计算，继而引发连锁反应。

对某一个节点k，distance[k]通常会发生会多次改变。