Java实现Dijkstra输出最短路径的实例

Java实现Dijkstra输出指定起点到终点的最短路径

前言：

最近在公司参加了一个比赛，其中涉及的一个问题，可以简化成如是描述：一个二维矩阵，每个点都有权重，需要找出从指定起点到终点的最短路径。

马上就想到了Dijkstra算法，所以又重新温故了一遍，这里给出Java的实现。

而输出最短路径的时候，在网上也进行了查阅，没发现什么标准的方法，于是在下面的实现中，我给出了一种能够想到的比较精简的方式：利用prev[]数组进行递归输出。

package graph.dijsktra;  import graph.model.Point;  import java.util.*;   public class Dijkstra {   private int[][] map; // 地图结构保存   private int[][] edges; // 邻接矩阵   private int[] prev; // 前驱节点标号   private boolean[] s; // S集合中存放到起点已经算出最短路径的点   private int[] dist; // dist[i]表示起点到第i个节点的最短路径   private int pointNum; // 点的个数   private Map<Integer, Point> indexPointMap; // 标号和点的对应关系   private Map<Point, Integer> pointIndexMap; // 点和标号的对应关系   private int v0; // 起点标号   private Point startPoint; // 起点   private Point endPoint; // 终点   private Map<Point, Point> pointPointMap; // 保存点和权重的映射关系   private List<Point> allPoints; // 保存所有点   private int maxX; // x坐标的最大值   private int maxY; // y坐标的最大值    public Dijkstra(int map[][], Point startPoint, Point endPoint) {     this.maxX = map.length;     this.maxY = map[0].length;     this.pointNum = maxX * maxY;     this.map = map;     this.startPoint = startPoint;     this.endPoint = endPoint;     init();     dijkstra();   }       public void printShortestPath() {     printDijkstra(pointIndexMap.get(endPoint));   }       private void init() {     // 初始化所有变量     edges = new int[pointNum][pointNum];     prev = new int[pointNum];     s = new boolean[pointNum];     dist = new int[pointNum];     indexPointMap = new HashMap<>();     pointIndexMap = new HashMap<>();     pointPointMap = new HashMap<>();     allPoints = new ArrayList<>();      // 将map二维数组中的所有点转换成自己的结构     int count = 0;     for (int x = 0; x < maxX; ++x) {       for (int y = 0; y < maxY; ++y) {         indexPointMap.put(count, new Point(x, y));         pointIndexMap.put(new Point(x, y), count);         count++;         allPoints.add(new Point(x, y));         pointPointMap.put(new Point(x, y), new Point(x, y, map[x][y]));       }     }      // 初始化邻接矩阵     for (int i = 0; i < pointNum; ++i) {       for (int j = 0; j < pointNum; ++j) {         if (i == j) {           edges[i][j] = 0;         } else {           edges[i][j] = 9999;         }       }     }      // 根据map上的权重初始化edges，当然这种算法是没有单独加起点的权重的     for (Point point : allPoints) {       for (Point aroundPoint : getAroundPoints(point)) {         edges[pointIndexMap.get(point)][pointIndexMap.get(aroundPoint)] = aroundPoint.getValue();       }     }      v0 = pointIndexMap.get(startPoint);      for (int i = 0; i < pointNum; ++i) {       dist[i] = edges[v0][i];       if (dist[i] == 9999) {         // 如果从0点（起点）到i点最短路径是9999，即不可达         // 则i节点的前驱节点不存在         prev[i] = -1;       } else {         // 初始化i节点的前驱节点为起点，因为这个时候有最短路径的都是与起点直接相连的点         prev[i] = v0;       }     }      dist[v0] = 0;     s[v0] = true;   }       private void dijkstra() {     for (int i = 1; i < pointNum; ++i) { // 此时有pointNum - 1个点在U集合中，需要循环pointNum - 1次       int minDist = 9999;       int u = v0;        for (int j = 1; j < pointNum; ++j) { // 在U集合中，找到到起点最短距离的点         if (!s[j] && dist[j] < minDist) { // 不在S集合，就是在U集合           u = j;           minDist = dist[j];         }       }       s[u] = true; // 将这个点放入S集合        for (int j = 1; j < pointNum; ++j) { // 以当前刚从U集合放入S集合的点u为基础，循环其可以到达的点         if (!s[j] && edges[u][j] < 9999) {           if (dist[u] + edges[u][j] < dist[j]) {             dist[j] = dist[u] + edges[u][j];             prev[j] = u;           }         }       }     }   }    private void printDijkstra(int endPointIndex) {     if (endPointIndex == v0) {       System.out.print(indexPointMap.get(v0) + ",");       return;     }     printDijkstra(prev[endPointIndex]);     System.out.print(indexPointMap.get(endPointIndex) + ",");   }    private List<Point> getAroundPoints(Point point) {     List<Point> aroundPoints = new ArrayList<>();     int x = point.getX();     int y = point.getY();     aroundPoints.add(pointPointMap.get(new Point(x - 1, y)));     aroundPoints.add(pointPointMap.get(new Point(x, y + 1)));     aroundPoints.add(pointPointMap.get(new Point(x + 1, y)));     aroundPoints.add(pointPointMap.get(new Point(x, y - 1)));     aroundPoints.removeAll(Collections.singleton(null)); // 剔除不在地图范围内的null点     return aroundPoints;   }    public static void main(String[] args) {     int map[][] = {         {1, 2, 2, 2, 2, 2, 2},         {1, 0, 2, 2, 0, 2, 2},         {1, 2, 0, 2, 0, 2, 2},         {1, 2, 2, 0, 2, 0, 2},         {1, 2, 2, 2, 2, 2, 2},         {1, 1, 1, 1, 1, 1, 1}     }; // 每个点都代表权重，没有方向限制     Point startPoint = new Point(0, 3); // 起点     Point endPoint = new Point(5, 6); // 终点     Dijkstra dijkstra = new Dijkstra(map, startPoint, endPoint);     dijkstra.printShortestPath();   } }