詳解Java中Dijkstra(迪傑斯特拉)演演算法的圖解與實現

public class MinHeap {
       List<int[][]> heap ;
       /**
        * 獲取並移除堆頂元素，並調整堆
        * @return
        */
       public int[][] pop() {
           int[][] top = heap.get(0);
           heap.set(0, heap.get(heap.size() - 1));
           heap.remove(heap.size() - 1);
           //調整堆
           this.adjust(0, heap.size() - 1);
           return top;
      }

       /**
        * 判斷是否為空
        * @return true/false
        */
       public boolean isEmpty() {
           if (null == this.heap) {
               return true;
          }
           if (this.heap.size() == 0) {
               return true;
          }
           return false;
      }
       /**
        * 修改index位置節點的value值，並調整最小堆（Java priorityQueue未提供）
        * @param index 修改節點位置
        * @param value 修改值
        */
       public void changeValue(int index, int value) {
           int src = heap.get(index)[0][1];
           heap.get(index)[0][1] = value;
           //直接比較當前值是變大還是變小,然後考慮是向上調整還是向下調整
           //則當前值可能往上移動
           if (src > value) {
               this.upAdjust(index);
               return;
          }
           this.adjust(index, heap.size() - 1);
      }

       public void upAdjust(int index) {
           //依次與雙親節點進行比較，小於雙親節點就直接交換。一直到根節點
           while (index > 0) {
               int parent = index >> 1;
               //雙親節點本來小於當前節點不需要進行調整
               if (heap.get(parent)[0][1] <= heap.get(index)[0][1]) {
                   break;
              }
               swap(index, parent);
               index = parent;
          }
      }
       
       /**
        * 初始化一個最小堆
        * @param nums
        */
       public void init(int[][] nums) {
           heap = new ArrayList<>(nums.length);
           for (int i = 0 ; i < nums.length; i ++) {
               int[][] temp = new int[1][2];
               temp[0][0] = nums[i][0];
               temp[0][1] = nums[i][1];
               heap.add(temp);
          }
           //從最後一個雙親節點開始將堆進行調整
           for (int i = nums.length / 2 ; i >= 0 ; -- i) {
               this.adjust(i, nums.length - 1);
          }
      }
       /**
        * 從當前index開始調節為最小堆
        * @param index 當前節點下標
        * @param end 最後一個節點下標
        */
       private void adjust(int index, int end) {
           //找到當前節點的孩子節點，將較小的節點與當前節點交換，一直往下，直至end
           while (index <= end) {
               //左孩子節點
               int left = index << 1;
               if (left + 1 <= end && heap.get(left + 1)[0][1] < heap.get(left)[0][1] ) {
                   //找到當前較小的節點
                   ++ left;
              }
               //沒有孩子節點，或者當前的孩子節點均已大於當前節點，已符合最小堆，不需要進行調整
               if (left > end || heap.get(index)[0][1] <= heap.get(left)[0][1]) {
                   break;
              }
               swap(index, left);
               index = left;
          }
      }
       private void swap(int i, int j) {
           int[][] temp = heap.get(i);
           heap.set(i, heap.get(j));
           heap.set(j, temp);
      }
  }

//節點
Node[] nodes;

//鄰接矩陣
int[][] adjacencyMatrix;
public class Node {
       private char value;
       Node(char value) {
           this.value = value;
      }
  }

private void initGraph(char[] values, String[] edges) {
       nodes = new Node[values.length];
//初始化node節點
       for (int i = 0 ; i < values.length ; i ++) {
           nodes[i] = new Node(values[i]);
      }
       adjacencyMatrix = new int[values.length][values.length];
//初始化鄰接表，同一個節點權重記為0，不相鄰節點權重記為Integer.MAX_VALUE
       for (int i = 0 ; i < values.length ; i++) {
           for (int j = 0 ; j < values.length ; j ++) {
               if (i == j) {
                   adjacencyMatrix[i][j] = 0;
                   continue;
              }
               adjacencyMatrix[i][j] = Integer.MAX_VALUE;
               adjacencyMatrix[j][i] = Integer.MAX_VALUE;
          }
      }
//根據edges更新相鄰節點權重值
       for (String edge : edges) {
           String[] node = edge.split(",");
           int i = Integer.valueOf(node[0]);
           int j = Integer.valueOf(node[1]);
           int weight = Integer.valueOf(node[2]);
           adjacencyMatrix[i][j] = weight;
           adjacencyMatrix[j][i] = weight;
      }
       visited = new boolean[nodes.length];

  }

/**
* 標誌對應下標節點是否已經處理，避免二次處理
*/
boolean[] visited;
   /**
    * 記錄已經求得的最短路徑 finallyNodes[0][0]記錄node下標，finallyNodes[0][1]記錄最短路徑長度
    */
   List<int[][]> finallyNodes;
   /**
    * 記錄求解過程目前的路徑長度，因為每次取當前已知最短，所以最小堆進行記錄
    * 但是java優先佇列沒有實現改變值，這裡需要自己實現
    * 首先每次取出堆頂元素之後，堆頂元素加入finallyNodes，此時需要更新與當前元素相鄰節點的路徑長度
    * 然後重新調整小根堆
    * 首先：只會更新變小的資料，所以從變小元素開始往上進行調整，或者直接呼叫調整方法，從堆頂往下進行調整
    */
   MinHeap processNodes;
/**
    * 初始化，主要初始化finallyNodes和processNodes，finallyNodes加入源節點，processNodes加入其他節點
    * @param nodeIndex
    */
   private void initDijkstra(int nodeIndex) {
       finallyNodes = new ArrayList<>(nodes.length);
       processNodes = new MinHeap();
       int[][] node = new int[1][2];
       node[0][0] = nodeIndex;
       node[0][1] = adjacencyMatrix[nodeIndex][nodeIndex];
       finallyNodes.add(node);
       visited[nodeIndex] = true;
       int[][] process = new int[nodes.length - 1][2];
       int j = 0;
       for (int i = 0 ; i < nodes.length ; i++) {
           if (i == nodeIndex) {
               continue;
          }
           process[j][0] = i;
           process[j][1] = adjacencyMatrix[nodeIndex][i];
           ++ j;
      }
       //初始化最小堆
       processNodes.init(process);
  }

public void dijkstra() {
       //1。堆頂取出最小元素，加入finallyNodes
//2。將與堆頂元素相連節點距離更新，
       while (!processNodes.isEmpty()) {
           int[][] head = processNodes.pop();
           finallyNodes.add(head);
           int nodeIndex = head[0][0];
           visited[nodeIndex] = true;
           //跟堆頂元素相鄰的元素
           for (int j = 0 ; j < nodes.length ; j ++) {
               //找到相鄰節點
               if (visited[j] || Integer.MAX_VALUE == adjacencyMatrix[nodeIndex][j]) {
                   continue;
              }
               for (int i = 0 ; i < processNodes.heap.size() ; i++) {
                   int[][] node = processNodes.heap.get(i);
                   //找到節點並且值變小，需要調整
                   if (node[0][0] == j && node[0][1] > head[0][1] + adjacencyMatrix[nodeIndex][j]) {
                       processNodes.changeValue(i, head[0][1] + adjacencyMatrix[nodeIndex][j]);
                       break;
                  }
              }
          }

      }
  }

public static void main(String[] args) {
       char[] values = new char[]{'A','B','C','D','E','F','G','H'};
       String[] edges = new String[]{"0,1,2","0,2,3","0,3,4","1,4,6","2,4,3","3,4,1","4,5,1","4,6,4","5,7,2","6,7,2"};
       Dijkstra dijkstra = new Dijkstra();
       dijkstra.initGraph(values, edges);
       int startNodeIndex = 0;
       dijkstra.initDijkstra(startNodeIndex);
       dijkstra.dijkstra();
       for (int[][] node : dijkstra.finallyNodes) {
           System.out.println(dijkstra.nodes[node[0][0]].value + "距離" + dijkstra.nodes[startNodeIndex].value + "最短路徑為：" + node[0][1]);
      }
  }