Dijkstra의 최단 경로 출력을 구현하는 Java의 방법 소개

이 글은 주로 Dijkstra를 구현하여 최단 경로를 출력하는 예제에 대한 관련 정보를 소개합니다. 도움이 필요한 친구들이 참고하면 좋겠습니다.

Java는 지정된 시작점에서 최단 경로를 출력하도록 Dijkstra를 구현합니다. point to the end point

머리말:

저는 최근 회사에서 열린 대회에 참가했습니다. 관련된 문제 중 하나는 다음과 같이 단순화할 수 있습니다. 2차원 행렬, 각 점에는 가중치가 있습니다. 지정된 시작점에서 끝점까지의 최단 경로를 찾는 것이 필요합니다.

다익스트라(Dijkstra) 알고리즘이 바로 생각나서 다시 한번 자바로 구현해봤습니다.

최단 경로를 출력할 때도 온라인에서 확인했지만 표준 방법을 찾지 못했습니다. 그래서 다음 구현에서는 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; 
  } 
}

위 내용은 Dijkstra의 최단 경로 출력을 구현하는 Java의 방법 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!