原标题：用Java实现Dijkstra输出指定起点到终点的最短路径
最近在公司参加了一个比赛，其中涉及的一个问题，可以简化成如是描述：一个二维矩阵，每个点都有权重，需要找出从指定起点到终点的最短路径。
马上就想到了Dijkstra算法，所以又重新温故了一遍，这里给出Java的实现。
而输出最短路径的时候，在网上也进行了查阅，没发现什么标准的方法，于是在下面的实现中，我给出了一种能够想到的比较精简的方式：利用prev[]数组进行递归输出。
[java]
view plaincopy
1.
package
graph.dijsktra;
3.
import
graph.model.Point;
5.
import
java.util.*;
7.
/**
8.
* Created by MHX on 2017/9/13.
9.
*/
10.
public
class
Dijkstra {
11.
private
int
[][] map;
// 地图结构保存
12.
private
int
[][] edges;
// 邻接矩阵
13.
private
int
[] prev;
// 前驱节点标号
14.
private
boolean
[] s;
// S集合中存放到起点已经算出最短路径的点
15.
private
int
[] dist;
// dist[i]表示起点到第i个节点的最短路径
16.
private
int
pointNum;
// 点的个数
17.
private
Map<Integer, Point> indexPointMap;
// 标号和点的对应关系
18.
private
Map<Point, Integer> pointIndexMap;
// 点和标号的对应关系
19.
private
int
v0;
// 起点标号
20.
private
Point startPoint;
// 起点
21.
private
Point endPoint;
// 终点
22.
private
Map<Point, Point> pointPointMap;
// 保存点和权重的映射关系
23.
private
List<Point> allPoints;
// 保存所有点
24.
private
int
maxX;
// x坐标的最大值
25.
private
int
maxY;
// y坐标的最大值
27.
public
Dijkstra(
int
map[][], Point startPoint, Point endPoint) {
28.
this
.maxX = map.length;
29.
this
.maxY = map[
0
].length;
30.
this
.pointNum = maxX * maxY;
31.
this
.map = map;
32.
this
.startPoint = startPoint;
33.
this
.endPoint = endPoint;
34.
init();
35.
dijkstra();
36.
}
38.
/**
39.
* 打印指定起点到终点的最短路径
40.
*/
41.
public
void
printShortestPath() {
42.
printDijkstra(pointIndexMap.get(endPoint));
43.
}
45.
/**
46.
* 初始化dijkstra
47.
*/
48.
private
void
init() {
49.
// 初始化所有变量
50.
edges =
new
int
[pointNum][pointNum];
51.
prev =
new
int
[pointNum];
52.
s =
new
boolean
[pointNum];
53.
dist =
new
int
[pointNum];
54.
indexPointMap =
new
HashMap<>();
55.
pointIndexMap =
new
HashMap<>();
56.
pointPointMap =
new
HashMap<>();
57.
allPoints =
new
ArrayList<>();
59.
// 将map二维数组中的所有点转换成自己的结构
60.
int
count =
0
;
61.
for
(
int
x =
0
; x < maxX; ++x) {
62.
for
(
int
y =
0
; y < maxY; ++y) {
63.
indexPointMap.put(count,
new
Point(x, y));
64.
pointIndexMap.put(
new
Point(x, y), count);
65.
count++;
66.
allPoints.add(
new
Point(x, y));
67.
pointPointMap.put(
new
Point(x, y),
new
Point(x, y, map[x][y]));
68.
}
69.
}
71.
// 初始化邻接矩阵
72.
for
(
int
i =
0
; i < pointNum; ++i) {
73.
for
(
int
j =
0
; j < pointNum; ++j) {
74.
if
(i == j) {
75.
edges[i][j] =
0
;
76.
}
else
{
77.
edges[i][j] =
9999
;
78.
}
79.
}
80.
}
82.
// 根据map上的权重初始化edges，当然这种算法是没有单独加起点的权重的
83.
for
(Point point : allPoints) {
84.
for
(Point aroundPoint : getAroundPoints(point)) {
85.
edges[pointIndexMap.get(point)][pointIndexMap.get(aroundPoint)] = aroundPoint.getValue();
86.
}
87.
}
89.
v0 = pointIndexMap.get(startPoint);
91.
for
(
int
i =
0
; i < pointNum; ++i) {
92.
dist[i] = edges[v0][i];
93.
if
(dist[i] ==
9999
) {
94.
// 如果从0点（起点）到i点最短路径是9999，即不可达
95.
// 则i节点的前驱节点不存在
96.
prev[i] = -
1
;
97.
}
else
{
98.
// 初始化i节点的前驱节点为起点，因为这个时候有最短路径的都是与起点直接相连的点
99.
prev[i] = v0;
100.
}
101.
}
103.
dist[v0] =
0
;
104.
s[v0] =
true
;
105.
}
107.
/**
108.
* dijkstra核心算法
109.
*/
110.
private
void
dijkstra() {
111.
for
(
int
i =
1
; i < pointNum; ++i) {
// 此时有pointNum - 1个点在U集合中，需要循环pointNum - 1次
112.
int
minDist =
9999
;
113.
int
u = v0;
115.
for
(
int
j =
1
; j < pointNum; ++j) {
// 在U集合中，找到到起点最短距离的点
116.
if
(!s[j] && dist[j] < minDist) {
// 不在S集合，就是在U集合
117.
u = j;
118.
minDist = dist[j];
119.
}
120.
}
121.
s[u] =
true
;
// 将这个点放入S集合
123.
for
(
int
j =
1
; j < pointNum; ++j) {
// 以当前刚从U集合放入S集合的点u为基础，循环其可以到达的点
124.
if
(!s[j] && edges[u][j] <
9999
) {
125.
if
(dist[u] + edges[u][j] < dist[j]) {
126.
dist[j] = dist[u] + edges[u][j];
127.
prev[j] = u;
128.
}
129.
}
130.
}
131.
}
132.
}
134.
private
void
printDijkstra(
int
endPointIndex) {
135.
if
(endPointIndex == v0) {
136.
System.out.print(indexPointMap.get(v0) +
","
);
137.
return
;
138.
}
139.
printDijkstra(prev[endPointIndex]);
140.
System.out.print(indexPointMap.get(endPointIndex) +
","
);
141.
}
143.
private
List<Point> getAroundPoints(Point point) {
144.
List<Point> aroundPoints =
new
ArrayList<>();
145.
int
x = point.getX();
146.
int
y = point.getY();
147.
aroundPoints.add(pointPointMap.get(
new
Point(x -
1
, y)));
148.
aroundPoints.add(pointPointMap.get(
new
Point(x, y +
1
)));
149.
aroundPoints.add(pointPointMap.get(
new
Point(x +
1
, y)));
150.
aroundPoints.add(pointPointMap.get(
new
Point(x, y -
1
)));
151.
aroundPoints.removeAll(Collections.singleton(
null
));
// 剔除不在地图范围内的null点
152.
return
aroundPoints;
153.
}
155.
public
static
void
main(String[] args) {
156.
int
map[][] = {
157.
{
1
,
2
,
2
,
2
,
2
,
2
,
2
},
158.
{
1
,
0
,
2
,
2
,
0
,
2
,
2
},
159.
{
1
,
2
,
0
,
2
,
0
,
2
,
2
},
160.
{
1
,
2
,
2
,
0
,
2
,
0
,
2
},
161.
{
1
,
2
,
2
,
2
,
2
,
2
,
2
},
162.
{
1
,
1
,
1
,
1
,
1
,
1
,
1
}
163.
};
// 每个点都代表权重，没有方向限制
164.
Point startPoint =
new
Point(
0
,
3
);
// 起点
165.
Point endPoint =
new
Point(
5
,
6
);
// 终点
166.
Dijkstra dijkstra =
new
Dijkstra(map, startPoint, endPoint);
167.
dijkstra.printShortestPath();
168.
}
169.
}
[java]
view plaincopy
1.
package
graph.model;
3.
public
class
Point {
4.
private
int
x;
5.
private
int
y;
6.
private
int
value;
8.
public
Point(
int
x,
int
y) {
9.
this
.x = x;
10.
this
.y = y;
11.
}
13.
public
Point(
int
x,
int
y,
int
value) {
14.
this
.x = x;
15.
this
.y = y;
16.
this
.value = value;
17.
}
19.
public
int
getX() {
20.
return
x;
21.
}
23.
public
void
setX(
int
x) {
24.
this
.x = x;
25.
}
27.
public
int
getY() {
28.
return
y;
29.
}
31.
public
void
setY(
int
y) {
32.
this
.y = y;
33.
}
35.
public
int
getValue() {
36.
return
value;
37.
}
39.
public
void
setValue(
int
value) {
40.
this
.value = value;
41.
}
43.
@Override
44.
public
String toString() {
45.
return
"{"
+
46.
"x="
+ x +
47.
", y="
+ y +
48.
'}'
;
49.
}
51.
@Override
52.
public
boolean
equals(Object o) {
53.
if
(
this
== o)
return
true
;
54.
if
(o ==
null
|| getClass() != o.getClass())
return
false
;
56.
Point point = (Point) o;
58.
if
(x != point.x)
return
false
;
59.
return
y == point.y;
60.
}
62.
@Override
63.
public
int
hashCode() {
64.
int
result = x;
65.
result =
31
* result + y;
66.
return
result;
67.
}
68.
}
返回搜狐，查看更多
责任编辑：
平台声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。
