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

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

前言：

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

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

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

package graph.dijsktra; 

import graph.model.Point; 

import java.util.*; 

/**
 * Created by MHX on 2017/9/13.
 */
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));
  } 

  /**
   * 初始化dijkstra
   */
  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;
  } 

  /**
   * dijkstra核心算法
   */
  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();
  }
}

package graph.model; 

public class Point {
  private int x;
  private int y;
  private int value; 

  public Point(int x, int y) {
    this.x = x;
    this.y = y;
  } 

  public Point(int x, int y, int value) {
    this.x = x;
    this.y = y;
    this.value = value;
  } 

  public int getX() {
    return x;
  } 

  public void setX(int x) {
    this.x = x;
  } 

  public int getY() {
    return y;
  } 

  public void setY(int y) {
    this.y = y;
  } 

  public int getValue() {
    return value;
  } 

  public void setValue(int value) {
    this.value = value;
  } 

  @Override
  public String toString() {
    return "{" +
        "x=" + x +
        ", y=" + y +
        '}';
  } 

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false; 

    Point point = (Point) o; 

    if (x != point.x) return false;
    return y == point.y;
  } 

  @Override
  public int hashCode() {
    int result = x;
    result = 31 * result + y;
    return result;
  }
}

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望通过本文能帮助到大家，谢谢大家对本站的支持！