服务器之家

服务器之家 > 正文

Java实现Dijkstra输出最短路径的实例

时间:2021-01-09 13:52     来源/作者:u012712087

Java实现Dijkstra输出指定起点到终点的最短路径

前言:

最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径。

马上就想到了Dijkstra算法,所以又重新温故了一遍,这里给出Java的实现。

而输出最短路径的时候,在网上也进行了查阅,没发现什么标准的方法,于是在下面的实现中,我给出了一种能够想到的比较精简的方式:利用prev[]数组进行递归输出。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
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();
  }
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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;
  }
}

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

原文链接:http://blog.csdn.net/u012712087/article/details/77995721

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部