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