前言：
最近在公司参加了一个比赛，其中涉及的一个问题，可以简化成如是描述：一个二维矩阵，每个点都有权重，需要找出从指定起点到终点的最短路径。
马上就想到了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
