1、Dijkstra算法

一、Dijkstra算法简介

  Dijkstra算法主要用于计算有权图的单源最短路径，Dijkstra算法的特点是从source结点开始，采用贪心算法的策略，每次贪心求得未访问的结点中，到source结点距离最近的结点（此时仍然有未访问的结点与source结点直接或间接相连，如果此时没有任何一个结点与source结点直接或间接相连，则结束循环），然后遍历贪心求得的结点的邻接点，更新距离集合。

二、代码实现

  比如，有如下的一个有向有权图，该有向有权图不能包含负值边和负值圈：

用Dijkstra算法找出以A为起点（A_{F表示上图中的0}5）的单源最短路径，步骤如下：

代码实现，如下所示：

package everydayPractice.greedyAlgorithm.dijkstra;

import java.util.ArrayDeque;
import java.util.Arrays;

public class Dijkstra {
   public static void main(String[] args) {
      Dijkstra object = new Dijkstra();
      int[][] matrix = {//用邻接矩阵表示图，0表示当前结点，-1表示结点之间没有直接的边，>0的正数表示结点之间边的权重
            {0, 6, 3, -1, -1, -1},
            {6, 0, 2, 5, -1, -1},
            {3, 2, 0, 3, 4, -1},
            {-1, 5, 3, 0, 2, 3},
            {-1, -1, 4, 2, 0, 5},
            {-1, -1, -1, 3, 5, 0}
      };
      int source = 2;
      int[][] result = object.getShortestPaths(matrix, source);//result[0]是距离，result[1]是路径
      System.out.println("结点" + source + "到图中所有结点之间的最短距离为：");
      for (int i = 0; i < result[0].length; i++)
         System.out.print(result[0][i] + " ");
      System.out.println();
      
      System.out.println("结点" + source + "到图中所有结点之间的最短路径为：");
      ArrayDeque stack = new ArrayDeque<>();//用堆栈保存结点路径
      int[] path = result[1];
      for (int i = 0; i < path.length; i++) {
         int temp = i;
         while (temp != source) {//沿当前结点的路径向上寻找，直到找到source结点
            stack.push(temp);
            temp = path[temp];
         }
         stack.push(source);
         while (!stack.isEmpty()) {//输出路径
            if (stack.size() > 1) {
               System.out.print(stack.poll() + "→");
            } else {
               System.out.print(stack.poll());
            }
         }
         System.out.println();

      }
   }

   public int[][] getShortestPaths(int[][] matrix, int source) {
      if (source < 0 || source >= matrix.length) {//起始点在图中
         return null;
      }
      int m = matrix.length;
      int n = matrix[0].length;
      int[] path = new int[m];//路径（存储上一个结点)
      Arrays.fill(path, -1);
      boolean[] vis = new boolean[m];//标记已访问过的结点
      int[] dist = new int[m];//距离source结点的距离，-1表示source结点与该结点不连通
      for (int i = 0; i < n; i++) {//先遍历source结点
         if (matrix[source][i] != -1) {
            path[i] = source;//与source结点直接相连的结点
         }
         dist[i] = matrix[source][i];
      }
      dist[source] = 0;
      vis[source] = true;
      path[source] = source;
      for (int i = 0; i < m; i++) {
         if (i == source) continue;
         int min = Integer.MAX_VALUE;//用于暂时存放source到其他结点的最短距离，初始化为0x7fffffff
         int idx = -1;
         for (int j = 0; j < m; j++) {//未访问的结点中，离source结点距离最短的结点（贪心求最小结点）
            if (!vis[j] && dist[j] != -1 && min > dist[j]) {
               min = dist[j];
               idx = j;
            }
         }
         if (idx == -1) break;//没有与source结点连通的结点，结束整个循环
         vis[idx] = true;//将贪心求到的最小结点，标记为已遍历，随后访问该结点（贪心结点的邻接点就是与source相连的结点）
         for (int j = 0; j < n; j++) {
            if (matrix[idx][j] != -1 && (dist[j] > min + matrix[idx][j] || dist[j] == -1)) {
               //更新贪心结点的邻接点到source结点的距离和路径
               dist[j] = min + matrix[idx][j];
               path[j] = idx;
            }
         }
      }
      return new int[][]{dist, path};
   }
}

运行结果，如下所示：