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; 
  } 
} 

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