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

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

# Java实现Dijkstra的最短路径  # Java实现Dijkstra的实例  # Java利用Dijkstra算法求解拓扑关系最短路径  # Java利用Dijkstra和Floyd分别求取图的最短路径  # java使用Dijkstra算法实现单源最短路径  # java实现dijkstra最短路径寻路算法  # java实现Dijkstra最短路径算法  # java实现最短路径算法之Dijkstra算法  # Java中Dijkstra算法求解最短路径的实现  # 最短  # 点到  # 递归  # 自己的  # 都是  # 都有  # 出了  # 如有  # 一遍  # 不存在  # 我给  # 这个时候  # 可达  # 一个问题  # 就想  # 谢谢大家  # 转换成  # 到第  # 进行了  # 组中 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 如何挑选优质建站一级代理提升网站排名？  Win11搜索栏无法输入_解决Win11开始菜单搜索没反应问题【技巧】  Laravel Session怎么存储_Laravel Session驱动配置详解  Laravel如何连接多个数据库_Laravel多数据库连接配置与切换教程  成都网站制作公司哪家好,四川省职工服务网是做什么用？  浅谈redis在项目中的应用  Laravel控制器是什么_Laravel MVC架构中Controller的作用与实践  如何挑选最适合建站的高性能VPS主机？  Android仿QQ列表左滑删除操作  如何在阿里云购买域名并搭建网站？  Swift中循环语句中的转移语句 break 和 continue  Laravel的Blade指令怎么自定义_创建你自己的Laravel Blade Directives  浅谈javascript alert和confirm的美化  Laravel与Inertia.js怎么结合_使用Laravel和Inertia构建现代单页应用  微信推文制作网站有哪些,怎么做微信推文，急？  如何在HTML表单中获取用户输入并用JavaScript动态控制复利计算循环  如何快速搭建高效香港服务器网站？  Laravel任务队列怎么用_Laravel Queues异步处理任务提升应用性能  如何在阿里云ECS服务器部署织梦CMS网站？  Laravel的.env文件有什么用_Laravel环境变量配置与管理详解  google浏览器怎么清理缓存_谷歌浏览器清除缓存加速详细步骤  Win11怎么关闭资讯和兴趣_Windows11任务栏设置隐藏小组件  Laravel如何创建自定义Artisan命令？（代码示例）  Laravel怎么定时执行任务_Laravel任务调度器Schedule配置与Cron设置【教程】  node.js报错：Cannot find module 'ejs'的解决办法  大连网站制作费用,大连新青年网站，五年四班里的视频怎样下载啊？  如何正确下载安装西数主机建站助手？  如何在阿里云域名上完成建站全流程？  进行网站优化必须要坚持的四大原则  Windows家庭版如何开启组策略(gpedit.msc)？（安装方法）  php结合redis实现高并发下的抢购、秒杀功能的实例  Laravel distinct去重查询_Laravel Eloquent去重方法  做企业网站制作流程,企业网站制作基本流程有哪些？  郑州企业网站制作公司,郑州招聘网站有哪些？  免费的流程图制作网站有哪些,2025年教师初级职称申报网上流程？  Android自定义listview布局实现上拉加载下拉刷新功能  如何快速搭建高效可靠的建站解决方案？  简历没回改：利用AI润色让你的文字更专业  Laravel怎么防止CSRF攻击_Laravel CSRF保护中间件原理与实践  如何在服务器上三步完成建站并提升流量？  如何在不使用负向后查找的情况下匹配特定条件前的换行符  高端智能建站公司优选：品牌定制与SEO优化一站式服务  Laravel项目如何进行性能优化_Laravel应用性能分析与优化技巧大全  如何快速搭建FTP站点实现文件共享？  Android利用动画实现背景逐渐变暗  百度浏览器如何管理插件 百度浏览器插件管理方法  nodejs redis 发布订阅机制封装实现方法及实例代码  小米17系列还有一款新机？主打6.9英寸大直屏和旗舰级影像  ChatGPT回答中断怎么办 引导AI继续输出完整内容的方法  谷歌浏览器下载文件时中断怎么办 Google Chrome下载管理修复