我通过三个函数 完成了这个功能
首先 创建哈希表 根据起始站名 终点站名
然后 根据哈希表 建立起 邻接表‘
最后 根据迪杰斯特拉算法 完成这个功能
/** * function:起终查询 */ // 构建邻接表 public static Map<String, Map<String, Integer>> buildAdjacencyList() { Connection connection = JDBCUtils.getConn(); Map<String, Map<String, Integer>> adjacencyList = new HashMap<>(); try { Statement statement = connection.createStatement(); ResultSet resultSet = statement.executeQuery("SELECT Starting_Station, Terminus_Station FROM station"); while (resultSet.next()) { String startingStation = resultSet.getString("Starting_Station"); String terminusStation = resultSet.getString("Terminus_Station"); addConnection(adjacencyList, startingStation, terminusStation); addConnection(adjacencyList, terminusStation, startingStation); } resultSet.close(); statement.close(); connection.close(); } catch (SQLException e) { e.printStackTrace(); // 适当处理 SQLException } return adjacencyList; } // 将连接添加到邻接表 private static void addConnection(Map<String, Map<String, Integer>> adjacencyList, String source, String destination) { if (!adjacencyList.containsKey(source)) { adjacencyList.put(source, new HashMap<>()); } adjacencyList.get(source).put(destination, 1); } //根据 buildAdjacencyList()函数 求邻接表 最短路径 public static List<String> shortest(User user) { String startingStation = user.getStarting_Station(); String terminusStation = user.getTerminus_Station(); Map<String, Map<String, Integer>> adjacencyList = buildAdjacencyList(); Map<String, Integer> distance = new HashMap<>(); Map<String, String> previous = new HashMap<>(); PriorityQueue<String> queue = new PriorityQueue<>(Comparator.comparingInt(distance::get)); for (String station : adjacencyList.keySet()) { distance.put(station, Integer.MAX_VALUE); previous.put(station, null); } distance.put(startingStation, 0); queue.add(startingStation); while (!queue.isEmpty()) { String currentStation = queue.poll(); if (currentStation.equals(terminusStation)) { break; // Found shortest path to terminus station } Map<String, Integer> neighbors = adjacencyList.get(currentStation); if (neighbors != null) { for (String neighbor : neighbors.keySet()) { int alt = distance.get(currentStation) + neighbors.get(neighbor); if (alt < distance.get(neighbor)) { distance.put(neighbor, alt); previous.put(neighbor, currentStation); queue.add(neighbor); } } } } // Reconstruct shortest path List<String> shortestPath = new ArrayList<>(); String current = terminusStation; while (previous.get(current) != null) { shortestPath.add(current); current = previous.get(current); } shortestPath.add(startingStation); Collections.reverse(shortestPath); System.out.println(shortestPath); return shortestPath; }
标签:distance,String,get,安卓,最短,Map,put,adjacencyList,app From: https://www.cnblogs.com/youxiandechilun/p/18104763