首頁 Java java教程 Java實作Dijkstra輸出最短路徑的方法介紹

Java實作Dijkstra輸出最短路徑的方法介紹

Sep 23, 2017 am 09:52 AM
java

這篇文章主要介紹了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 + 
        &#39;}&#39;; 
  } 
 
  @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; 
  } 
}
登入後複製

以上是Java實作Dijkstra輸出最短路徑的方法介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前 By 尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根

Java 中的完美數 Java 中的完美數 Aug 30, 2024 pm 04:28 PM

Java 中的完美數

Java 中的隨機數產生器 Java 中的隨機數產生器 Aug 30, 2024 pm 04:27 PM

Java 中的隨機數產生器

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java中的Weka

Java 中的阿姆斯壯數 Java 中的阿姆斯壯數 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯壯數

Java 中的史密斯數 Java 中的史密斯數 Aug 30, 2024 pm 04:28 PM

Java 中的史密斯數

Java Spring 面試題 Java Spring 面試題 Aug 30, 2024 pm 04:29 PM

Java Spring 面試題

突破或從Java 8流返回? 突破或從Java 8流返回? Feb 07, 2025 pm 12:09 PM

突破或從Java 8流返回?

See all articles