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:[email protected]
 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:[email protected]
 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：https://wenku.baidu.com/view/9fdeaa3c2b160b4e767fcff7.html

小結：

最重要的是記住：在搜索過程中，若節點i對應的distance[i]發生改變，那麼對其任意一個鄰居節點j，對應的distance[j]都要重新計算，繼而引發連鎖反應。

對某一個節點k，distance[k]通常會發生會多次改變。