前言：
最近在公司參加了一個比賽，其中涉及的一個問題，可以簡化成如是描述：一個二維矩陣，每個點都有權重，需要找出從指定起點到終點的最短路徑。
馬上就想到了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
