Einführung in die Java-Methode zur Implementierung der Dijkstra-Ausgabe des kürzesten Pfades

In diesem Artikel werden hauptsächlich relevante Informationen zu Beispielen für die Implementierung des kürzesten Ausgabepfads von Dijkstra vorgestellt. Ich hoffe, dass dieser Artikel jedem helfen kann, der Hilfe benötigt Der kürzeste Weg zum Endpunkt

Vorwort:

Ich habe kürzlich an einem Wettbewerb im Unternehmen teilgenommen und ein damit verbundenes Problem kann vereinfacht werden Diese Beschreibung: Eine zweidimensionale Matrix, jeder Punkt hat ein Gewicht und Sie müssen den kürzesten Weg von einem angegebenen Startpunkt zu einem Endpunkt finden.

Ich habe sofort an den Dijkstra-Algorithmus gedacht und ihn noch einmal überprüft. Hier ist die Implementierung in Java.

Bei der Ausgabe des kürzesten Pfades habe ich auch online nachgesehen und keine Standardmethode gefunden, daher habe ich in der folgenden Implementierung eine einfachere Methode angegeben, die mir einfällt: Verwenden Sie das prev[]-Array für rekursive Ausgabe.

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

Das obige ist der detaillierte Inhalt vonEinführung in die Java-Methode zur Implementierung der Dijkstra-Ausgabe des kürzesten Pfades. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!