Java Dijkstra出力の最短経路の例を実現します。
JavaはDijkstra出力指定の起点から終点までの最短ルートを実現します。
前言:
最近会社で試合に参加しましたが、その中の一つの問題は、例えば説明を簡略化することができます。一つの二次元マトリックスは、各点に重みがあります。指定された起点から終点までの最短ルートを探し出す必要があります。
すぐにDijkstraアルゴリズムを思い出しました。だからもう一度復習しました。ここでJavaの実現を提供します。
出力が一番短いパスの時、インターネットでも調べましたが、標準的な方法が見つからないので、下記の実現において、考えられる比較的簡単な方法を提供しました。prev[]配列を利用して再帰的に出力します。
前言:
最近会社で試合に参加しましたが、その中の一つの問題は、例えば説明を簡略化することができます。一つの二次元マトリックスは、各点に重みがあります。指定された起点から終点までの最短ルートを探し出す必要があります。
すぐにDijkstraアルゴリズムを思い出しました。だからもう一度復習しました。ここでJavaの実現を提供します。
出力が一番短いパスの時、インターネットでも調べましたが、標準的な方法が見つからないので、下記の実現において、考えられる比較的簡単な方法を提供しました。prev[]配列を利用して再帰的に出力します。
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();
}
}
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;
}
}