Dijkstra求最短路径

    xiaoxiao2021-12-15  34

    package org.test; import java.util.Collections; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.LinkedList; import java.util.Map; import java.util.Map.Entry; import java.util.Optional; import java.util.Random; public class MyDijkstra { private final int m_max = Integer.MAX_VALUE; private int m_total; private int[][] m_matirx; private int[] m_mark; private Map<String,Map<String,Integer>> m_line; private Map<String,Integer> m_nodesPos = new HashMap<String,Integer>(); /** * * @param nodes 所有的顶点 * @param line 所有直接相连顶点间的距离(双向) */ public MyDijkstra(String[] nodes,Map<String,Map<String,Integer>> line) { this.m_total = nodes.length; m_matirx = new int[this.m_total][this.m_total]; m_mark = new int[m_total]; for(int i = 0; i < m_total; i++) { for(int j = 0; j < m_total; j++) { if (i == j) { m_matirx[i][j] = 0; } else { m_matirx[i][j] = m_max; } } m_nodesPos.put(nodes[i], i); } line.forEach((id1,lines)->{ lines.forEach((id2,length)->{ m_matirx[m_nodesPos.get(id1)][m_nodesPos.get(id2)] = length; }); }); m_line = line; } private void printMatirx() { for (int i = 0; i < m_total; i++) { for(int j = 0; j < m_total; j++) { if (this.m_matirx[i][j] == this.m_max) { System.out.print(" ∞ " + "-"); } else { System.out.print(String.format("d", this.m_matirx[i][j]) + "-"); } } System.out.print("\n"); } } private String getShortestDirectlyConnected(String s,String e) throws Exception { int minLength = this.m_max; String ret = null; for(String p1 : m_line.keySet()) { if (p1.equals(e)) { Map<String,Integer> line1 = m_line.get(p1); for(String p2 : line1.keySet()) { int length = this.m_matirx[this.m_nodesPos.get(s)][this.m_nodesPos.get(p2)] + this.m_line.get(e).get(p2); if (length < minLength) { minLength = length; ret = p2; } } return ret; } } throw new Exception("imposiable"); } private LinkedList<String> getShortestRoadLine(String s,String e) { LinkedList<String> ret = new LinkedList<String>(); if (s.equals(e)) { return ret; } String end = e; ret.add(e); try { while(true) { String mid = getShortestDirectlyConnected(s,end); ret.add(mid); //System.out.println("------->" + s + "," + end + "," + mid); if (mid.equals(s)) { Collections.reverse(ret); return ret; } end = mid; } } catch (Exception ex) { return ret; } } public Optional <LinkedList<String>> getShortestRoad(String str,String etr) { int s = this.m_nodesPos.get(str); int e = this.m_nodesPos.get(etr); int [] dis = new int[m_total]; for(int i = 0; i < this.m_total; i++) { m_mark[i] = 0; dis[i] = this.m_matirx[s][i]; } dis[s] = 0; this.m_mark[s] = 1; int min = -1; int k = -1; for(int i = 0; i < this.m_total; i++) { min = this.m_max; for(int j = 0; j < this.m_total; j++) { if (this.m_mark[j] == 0 && dis[j] < min) { min = dis[j]; k = j; } } //取出了下一个距离s路径最近的点,可能s直接是孤立点 if (k == -1) { return Optional.ofNullable(null); } this.m_mark[k] = 1; //修正以前的结果(j到原点的距离可能随着新的k距离的更新有更短的路径出现,所以要更新j到s的路径长度) for(int j = 0; j < this.m_total; j++) { if (this.m_mark[j] == 0 && (this.m_matirx[k][j] + dis[k]) > 0 && (this.m_matirx[k][j] + dis[k]) < dis[j]) { dis[j] = this.m_matirx[k][j] + dis[k]; this.m_matirx[s][j] = dis[j]; } } } if (dis[e] == this.m_max) { return Optional.ofNullable(null); } //this.printMatirx(); return Optional.of(getShortestRoadLine(str,etr)); } public static void main(String[] args) { String[] points = {"1","2","3","4","5","6","7","8","9"}; Map<String,Map<String,Integer>> line = new HashMap<String,Map<String,Integer>>(); line.put("1", new HashMap<String,Integer>()); line.get("1").put("2", 4); line.get("1").put("4", 2); line.get("1").put("3", 5); line.put("2", new HashMap<String,Integer>()); line.get("2").put("1", 4); line.get("2").put("5", 3); line.put("3", new HashMap<String,Integer>()); line.get("3").put("1", 5); line.get("3").put("6", 7); line.put("4", new HashMap<String,Integer>()); line.get("4").put("7", 5); line.get("4").put("1", 2); line.put("5", new HashMap<String,Integer>()); line.get("5").put("2", 3); line.get("5").put("7", 9); line.get("5").put("8", 4); line.put("6", new HashMap<String,Integer>()); line.get("6").put("3", 7); line.get("6").put("7", 1); line.put("7", new HashMap<String,Integer>()); line.get("7").put("6", 1); line.get("7").put("5", 9); line.get("7").put("4", 5); line.put("8", new HashMap<String,Integer>()); line.get("8").put("5", 4); line.get("8").put("9", 3); line.put("9", new HashMap<String,Integer>()); line.get("9").put("8", 3); MyDijkstra o = new MyDijkstra(points,line); Optional <LinkedList<String>> road = o.getShortestRoad("1","6"); if (road.isPresent()) { System.out.println("road--->" + road.get()); } else { System.out.println("can not find road"); } } //模拟矩阵块的最短寻路 // public static void main(String[] args) // { // int width = 50; // int height = 50; // int startX = 0; // int startY = 0; // int endX = 45; // int endY = 48; // int[][] rect = new int[width][height]; // for(int i = 0; i < width; i++) // { // for(int j = 0; j < height ; j++) // { // rect[i][j] = 1; // } // } // // rect[startX][startY] = 2;//起点 // rect[endX][endY] = 3;//终点 // Random r1 = new Random(System.currentTimeMillis()); // // //障碍,不能通过 // for(int i = 0; i < 500; i++) // { // int randX = Math.abs(r1.nextInt() % width); // int randY = Math.abs(r1.nextInt() % height); // if (rect[randX][randY] == 1) // { // rect[randX][randY] = 4; // } // } // // LinkedHashMap<String,int[]> listMap = new LinkedHashMap<String,int[]>(); // int pos = 0; // // for(int i = 0; i < width;i++) // { // for (int j = 0; j < height;j++) // { // if (rect[i][j] != 4) // { // listMap.put(i + "_" + j, new int[]{i,j,pos++}); // } // } // } // // Map<String,Map<String,Integer>> line = new HashMap<String,Map<String,Integer>>(); // // listMap.forEach((id,node)->{ // line.put(id, new HashMap<String,Integer>()); // String id1 = node[0] + "_" + (node[1] + 1); // String id2 = node[0] + "_" + (node[1] - 1); // String id3 = (node[0] + 1) + "_" + node[1]; // String id4 = (node[0] - 1) + "_" + node[1]; // if (listMap.containsKey(id1)) // { // line.get(id).put(id1, 1); // } // if (listMap.containsKey(id2)) // { // line.get(id).put(id2, 1); // } // if (listMap.containsKey(id3)) // { // line.get(id).put(id3, 1); // } // if (listMap.containsKey(id4)) // { // line.get(id).put(id4, 1); // } // }); // // String[] node = new String[listMap.size()]; // // pos = 0; // // for(Entry<String,int[]> entry : listMap.entrySet()) // { // node[pos++] = entry.getKey(); // } // // MyDijkstra o = new MyDijkstra(node,line); // Optional <LinkedList<String>> road = o.getShortestRoad(startX + "_" + startY,endX + "_" + endY); // if (!road.isPresent()) // { // System.out.println("can not find shortest road"); // return; // } // road.get().forEach(p->{ // int[] mapP = listMap.get(p); // if (rect[mapP[0]][mapP[1]] == 1) // { // rect[mapP[0]][mapP[1]] = 0; // } // }); // for(int i = 0; i < width;i++) // { // for (int j = 0; j < height;j++) // { // System.out.print(rect[i][j] + " "); // } // System.out.print("\n"); // } // } }
    转载请注明原文地址: https://ju.6miu.com/read-1000185.html

    最新回复(0)