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;
private
int
[] dist;
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;
private
int
maxY;
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<>();
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
;
}
}
}
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
) {
prev[i] = -
1
;
}
else
{
prev[i] = v0;
}
}
dist[v0] =
0
;
s[v0] =
true
;
}
/**
* dijkstra核心算法
*/
private
void
dijkstra() {
for
(
int
i =
1
; i < pointNum; ++i) {
int
minDist =
9999
;
int
u = v0;
for
(
int
j =
1
; j < pointNum; ++j) {
if
(!s[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
s[u] =
true
;
for
(
int
j =
1
; j < pointNum; ++j) {
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
));
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();
}
}