Java实现Dijkstra输出最短路径的实例
程序员文章站
2024-03-02 13:43:46
java实现dijkstra输出指定起点到终点的最短路径
前言:
最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找...
java实现dijkstra输出指定起点到终点的最短路径
前言:
最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径。
马上就想到了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; } }
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望通过本文能帮助到大家,谢谢大家对本站的支持!