/** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 * 描述： Floyd-Warshall Algorithms * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/12 - 14:01 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : City.java * explain : 学习 类 **/ package FloydWarshall; /** * 城市实体 * */ public class City { public String name; public float x; public float y; public City(String name, float x, float y) { this.name = name; this.x = x; this.y = y; } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 * 描述： Floyd-Warshall Algorithms * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/12 - 14:04 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : FloydRoadGraph.java * explain : 学习 类 **/ package FloydWarshall; import javax.imageio.ImageIO; import java.awt.*; import java.awt.image.BufferedImage; import java.io.File; import java.io.FileOutputStream; import java.util.*; import java.util.List; import java.util.stream.Collectors; /** * Floyd-Warshall 路网矩阵 * */ public class FloydRoadGraph { private final double INF = Double.MAX_VALUE / 2; public List<String> cityNames; public Map<String, Integer> nameToIdx; private int n; public double[][] distMatrix; public int[][] prevMatrix; public FloydRoadGraph(List<String> cityList) { cityNames = cityList; n = cityList.size(); nameToIdx = new HashMap<>(); for (int i = 0; i < n; i++) { nameToIdx.put(cityList.get(i), i); } // 初始化矩阵 distMatrix = new double[n][n]; prevMatrix = new int[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(distMatrix[i], INF); Arrays.fill(prevMatrix[i], -1); distMatrix[i][i] = 0; } } // 添加双向边 public void addEdge(String from, String to, double weight) { int u = nameToIdx.get(from); int v = nameToIdx.get(to); distMatrix[u][v] = weight; distMatrix[v][u] = weight; prevMatrix[u][v] = u; prevMatrix[v][u] = v; } // 执行Floyd全源最短路 public void runFloyd() { int size = n; double[][] d = new double[size][size]; int[][] p = new int[size][size]; for (int i = 0; i < size; i++) { System.arraycopy(distMatrix[i], 0, d[i], 0, size); System.arraycopy(prevMatrix[i], 0, p[i], 0, size); } for (int k = 0; k < size; k++) { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (d[i][k] + d[k][j] < d[i][j]) { d[i][j] = d[i][k] + d[k][j]; p[i][j] = p[k][j]; } } } } distMatrix = d; prevMatrix = p; } // 回溯路径，过滤禁行城市 public Pair<Double, List<String>> getPath(String start, String end, Set<String> banSet) { if (!nameToIdx.containsKey(start) || !nameToIdx.containsKey(end)) { return new Pair<>(INF, new ArrayList<>()); } int u = nameToIdx.get(start); int v = nameToIdx.get(end); if (distMatrix[u][v] >= INF) { return new Pair<>(INF, new ArrayList<>()); } List<Integer> idxPath = new ArrayList<>(); int cur = v; while (cur != -1) { idxPath.add(cur); cur = prevMatrix[u][cur]; } Collections.reverse(idxPath); List<String> namePath = new ArrayList<>(); for (int idx : idxPath) { String city = cityNames.get(idx); if (banSet.contains(city)) { return new Pair<>(INF, new ArrayList<>()); } namePath.add(city); } return new Pair<>(distMatrix[u][v], namePath); } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 * 描述： Floyd-Warshall Algorithms * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/12 - 14:06 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : FloydPathPlanner.java * explain : 学习 类 **/ package FloydWarshall; import javax.imageio.ImageIO; import java.awt.*; import java.awt.geom.Ellipse2D; import java.awt.image.BufferedImage; import java.io.File; import java.io.FileOutputStream; import java.util.*; import java.util.List; import java.util.stream.Collectors; /** * 路径规划器：约束 + 绘图 * */ public class FloydPathPlanner { private final FloydRoadGraph graph; private final Map<String, City> cityMap; public List<String> mustPassCities = new ArrayList<>(); public Set<String> banCities = new HashSet<>(); public FloydPathPlanner(FloydRoadGraph graph, Map<String, City> cityMap) { this.graph = graph; this.cityMap = cityMap; } // 计算路线，校验必经城市 public Pair<Double, List<String>> calculateRoute(String start, String end) { Pair<Double, List<String>> res = graph.getPath(start, end, banCities); List<String> path = res.getValue(); if (path.isEmpty()) { return new Pair<>(Double.MAX_VALUE, new ArrayList<>()); } for (String req : mustPassCities) { if (!path.contains(req)) { return new Pair<>(Double.MAX_VALUE, new ArrayList<>()); } } return res; } // 生成PNG图片，修复fillEllipse浮点参数报错 public void drawMap(String savePath, List<String> highlightRoute) throws Exception { int width = 2800; int height = 1300; float offsetX = 400f; float offsetY = 20f; float scale = 70f; float nodeRadius = 8f; BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_3BYTE_BGR); Graphics2D g2d = image.createGraphics(); g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); g2d.setColor(Color.WHITE); g2d.fillRect(0, 0, width, height); // 中文字体 Windows微软雅黑 Font font = new Font("Microsoft YaHei", Font.PLAIN, 11); g2d.setFont(font); BasicStroke strokeNormal = new BasicStroke(1); BasicStroke strokeRed = new BasicStroke(4); // 绘制普通道路，去重双向边 Set<String> drawnEdge = new HashSet<>(); for (String frm : graph.cityNames) { City cFrom = cityMap.get(frm); float fx = cFrom.x * scale + offsetX; float fy = height - (cFrom.y * scale + offsetY); for (String to : graph.cityNames) { String k1 = frm + "|" + to; String k2 = to + "|" + frm; if (drawnEdge.contains(k1) || drawnEdge.contains(k2)) continue; int u = graph.nameToIdx.get(frm); int v = graph.nameToIdx.get(to); if (graph.distMatrix[u][v] >= Double.MAX_VALUE / 2) continue; drawnEdge.add(k1); City cTo = cityMap.get(to); float tx = cTo.x * scale + offsetX; float ty = height - (cTo.y * scale + offsetY); g2d.setColor(Color.GRAY); g2d.setStroke(strokeNormal); g2d.drawLine((int) fx, (int) fy, (int) tx, (int) ty); } } // 绘制红色高亮路径 g2d.setColor(Color.RED); g2d.setStroke(strokeRed); for (int i = 0; i < highlightRoute.size() - 1; i++) { String a = highlightRoute.get(i); String b = highlightRoute.get(i + 1); City ca = cityMap.get(a); City cb = cityMap.get(b); float ax = ca.x * scale + offsetX; float ay = height - (ca.y * scale + offsetY); float bx = cb.x * scale + offsetX; float by = height - (cb.y * scale + offsetY); g2d.drawLine((int) ax, (int) ay, (int) bx, (int) by); } // 绘制城市圆点【修复点：使用Ellipse2D.Float支持浮点坐标】 for (City city : cityMap.values()) { float x = city.x * scale + offsetX; float y = height - (city.y * scale + offsetY); // 构建浮点椭圆图形 Ellipse2D.Float ellipse = new Ellipse2D.Float( x - nodeRadius, y - nodeRadius, nodeRadius * 2, nodeRadius * 2 ); g2d.setColor(Color.BLUE); g2d.fill(ellipse); // 文字上浮，不遮挡圆点 g2d.setColor(Color.BLACK); g2d.drawString(city.name, x + 4, y - nodeRadius - 14); } g2d.dispose(); // 保存图片 FileOutputStream fos = new FileOutputStream(new File(savePath)); ImageIO.write(image, "png", fos); fos.close(); System.out.println("✅ 路网图片已保存：" + new File(savePath).getAbsolutePath()); } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 * 描述： Floyd-Warshall Algorithms * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/12 - 14:03 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : Pair.java * explain : 学习 类 **/ package FloydWarshall; /** * * 二元组 存储距离+路径 * */ public class Pair<K extends Comparable<K>, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } }

/** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 * 描述： Floyd-Warshall Algorithms * Author : geovindu,Geovin Du 涂聚文. * IDE : IntelliJ IDEA 2024.3.6 Java 17 * # database : Oracle21c,MySQL 9.0,SQL Server 2019,PostgreSQL 17.1 Neo4j * # OS : window10 * Datetime : 2026 - 2026/7/12 - 11:33 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : FloydWarshallBll.java * explain : 学习 类 **/ package Bll; import FloydWarshall.*; import javax.imageio.ImageIO; import java.awt.*; import java.awt.geom.Ellipse2D; import java.awt.image.BufferedImage; import java.io.File; import java.io.FileOutputStream; import java.util.*; import java.util.List; import java.util.stream.Collectors; /** * * **/ public class FloydWarshallBll { // 拼接路径字符串 public static String joinPath(List<String> path) { if (path.isEmpty()) return "无路线"; return String.join(" → ", path); } // 解析顿号分隔输入 public static List<String> parseCityStr(String input) { if (input == null || input.isBlank()) return new ArrayList<>(); return Arrays.stream(input.split("、")) .map(String::trim) .filter(s -> !s.isBlank()) .collect(Collectors.toList()); } public void demo() { System.out.println("=== 执行 FloydWarshall 全源最短路径算法示例 ==="); // 城市坐标数据 Map<String, City> cityData = new HashMap<>(); cityData.put("深圳", new City("深圳", 5, 0)); cityData.put("惠州", new City("惠州", 6, 1)); cityData.put("东莞", new City("东莞", 4, 0)); cityData.put("广州", new City("广州", 3, 0)); cityData.put("佛山", new City("佛山", 2, 0)); cityData.put("肇庆", new City("肇庆", 1, 1)); cityData.put("梧州", new City("梧州", -2, 2)); cityData.put("桂林", new City("桂林", -3, 4)); cityData.put("柳州", new City("柳州", -4, 3)); cityData.put("南宁", new City("南宁", -5, 1)); cityData.put("韶关", new City("韶关", 2, 4)); cityData.put("河源", new City("河源", 7, 3)); cityData.put("赣州", new City("赣州", 8, 6)); cityData.put("吉安", new City("吉安", 9, 9)); cityData.put("南昌", new City("南昌", 10, 8)); cityData.put("萍乡", new City("萍乡", 7, 8)); cityData.put("长沙", new City("长沙", 6, 9)); cityData.put("株洲", new City("株洲", 6, 8)); cityData.put("衡阳", new City("衡阳", 6, 6)); cityData.put("郴州", new City("郴州", 6, 4)); cityData.put("九江", new City("九江", 11, 9)); cityData.put("武汉", new City("武汉", 9, 11)); cityData.put("郑州", new City("郑州", 10, 14)); cityData.put("西安", new City("西安", 7, 15)); cityData.put("福州", new City("福州", 13, 7)); cityData.put("厦门", new City("厦门", 14, 4)); List<String> cityList = new ArrayList<>(cityData.keySet()); // 1. 里程路网 KM FloydRoadGraph graphKm = new FloydRoadGraph(cityList); graphKm.addEdge("深圳", "惠州", 75); graphKm.addEdge("深圳", "广州", 140); graphKm.addEdge("深圳", "东莞", 65); graphKm.addEdge("惠州", "河源", 90); graphKm.addEdge("东莞", "广州", 50); graphKm.addEdge("广州", "韶关", 190); graphKm.addEdge("广州", "佛山", 25); graphKm.addEdge("佛山", "肇庆", 70); graphKm.addEdge("肇庆", "梧州", 210); graphKm.addEdge("梧州", "桂林", 260); graphKm.addEdge("桂林", "柳州", 170); graphKm.addEdge("柳州", "南宁", 220); graphKm.addEdge("韶关", "赣州", 230); graphKm.addEdge("河源", "赣州", 180); graphKm.addEdge("赣州", "吉安", 240); graphKm.addEdge("赣州", "南昌", 390); graphKm.addEdge("吉安", "南昌", 215); graphKm.addEdge("吉安", "萍乡", 280); graphKm.addEdge("萍乡", "长沙", 150); graphKm.addEdge("长沙", "武汉", 280); graphKm.addEdge("长沙", "株洲", 60); graphKm.addEdge("株洲", "衡阳", 130); graphKm.addEdge("衡阳", "郴州", 180); graphKm.addEdge("郴州", "韶关", 150); graphKm.addEdge("南昌", "九江", 130); graphKm.addEdge("九江", "武汉", 200); graphKm.addEdge("武汉", "郑州", 470); graphKm.addEdge("郑州", "西安", 450); graphKm.addEdge("南昌", "福州", 380); graphKm.addEdge("福州", "厦门", 230); graphKm.runFloyd(); // 2. 耗时路网 Hour FloydRoadGraph graphHour = new FloydRoadGraph(cityList); graphHour.addEdge("深圳", "惠州", 1.0); graphHour.addEdge("深圳", "广州", 1.8); graphHour.addEdge("深圳", "东莞", 0.8); graphHour.addEdge("惠州", "河源", 1.3); graphHour.addEdge("东莞", "广州", 0.7); graphHour.addEdge("广州", "韶关", 2.2); graphHour.addEdge("广州", "佛山", 0.4); graphHour.addEdge("佛山", "肇庆", 0.9); graphHour.addEdge("肇庆", "梧州", 2.5); graphHour.addEdge("梧州", "桂林", 3.0); graphHour.addEdge("桂林", "柳州", 2.0); graphHour.addEdge("柳州", "南宁", 2.5); graphHour.addEdge("韶关", "赣州", 2.7); graphHour.addEdge("河源", "赣州", 2.0); graphHour.addEdge("赣州", "吉安", 2.6); graphHour.addEdge("赣州", "南昌", 4.2); graphHour.addEdge("吉安", "南昌", 2.3); graphHour.addEdge("吉安", "萍乡", 3.0); graphHour.addEdge("萍乡", "长沙", 1.6); graphHour.addEdge("长沙", "武汉", 3.0); graphHour.addEdge("长沙", "株洲", 0.8); graphHour.addEdge("株洲", "衡阳", 1.4); graphHour.addEdge("衡阳", "郴州", 2.0); graphHour.addEdge("郴州", "韶关", 1.7); graphHour.addEdge("南昌", "九江", 1.4); graphHour.addEdge("九江", "武汉", 2.1); graphHour.addEdge("武汉", "郑州", 4.8); graphHour.addEdge("郑州", "西安", 4.3); graphHour.addEdge("南昌", "福州", 4.0); graphHour.addEdge("福州", "厦门", 2.4); graphHour.runFloyd(); // 3. 路费路网 Cost FloydRoadGraph graphCost = new FloydRoadGraph(cityList); graphCost.addEdge("深圳", "惠州", 35); graphCost.addEdge("深圳", "广州", 65); graphCost.addEdge("深圳", "东莞", 30); graphCost.addEdge("惠州", "河源", 42); graphCost.addEdge("东莞", "广州", 25); graphCost.addEdge("广州", "韶关", 85); graphCost.addEdge("广州", "佛山", 15); graphCost.addEdge("佛山", "肇庆", 35); graphCost.addEdge("肇庆", "梧州", 100); graphCost.addEdge("梧州", "桂林", 120); graphCost.addEdge("桂林", "柳州", 70); graphCost.addEdge("柳州", "南宁", 95); graphCost.addEdge("韶关", "赣州", 105); graphCost.addEdge("河源", "赣州", 80); graphCost.addEdge("赣州", "吉安", 110); graphCost.addEdge("赣州", "南昌", 180); graphCost.addEdge("吉安", "南昌", 95); graphCost.addEdge("吉安", "萍乡", 125); graphCost.addEdge("萍乡", "长沙", 65); graphCost.addEdge("长沙", "武汉", 130); graphCost.addEdge("长沙", "株洲", 25); graphCost.addEdge("株洲", "衡阳", 55); graphCost.addEdge("衡阳", "郴州", 80); graphCost.addEdge("郴州", "韶关", 65); graphCost.addEdge("南昌", "九江", 55); graphCost.addEdge("九江", "武汉", 85); graphCost.addEdge("武汉", "郑州", 210); graphCost.addEdge("郑州", "西安", 190); graphCost.addEdge("南昌", "福州", 170); graphCost.addEdge("福州", "厦门", 105); graphCost.runFloyd(); // 规划器实例 FloydPathPlanner planKm = new FloydPathPlanner(graphKm, cityData); FloydPathPlanner planHour = new FloydPathPlanner(graphHour, cityData); FloydPathPlanner planCost = new FloydPathPlanner(graphCost, cityData); System.out.println("===== Java JDK17 Floyd-Warshall 全源路径规划系统 ====="); System.out.println("可用城市：" + String.join("、", cityList)); System.out.println("----------------------------------------"); Scanner sc = new Scanner(System.in); System.out.print("输入起点城市："); String start = sc.nextLine().trim(); System.out.print("输入终点城市："); String end = sc.nextLine().trim(); System.out.print("必须途经城市（多城顿号分隔，无直接回车）："); String mustInput = sc.nextLine().trim(); System.out.print("禁止绕行城市（多城顿号分隔，无直接回车）："); String banInput = sc.nextLine().trim(); sc.close(); List<String> mustList = parseCityStr(mustInput); List<String> banList = parseCityStr(banInput); // 绑定约束 Runnable bindConstraint = () -> { planKm.mustPassCities = new ArrayList<>(mustList); planKm.banCities = new HashSet<>(banList); planHour.mustPassCities = new ArrayList<>(mustList); planHour.banCities = new HashSet<>(banList); planCost.mustPassCities = new ArrayList<>(mustList); planCost.banCities = new HashSet<>(banList); }; bindConstraint.run(); // 计算路线 Pair<Double, List<String>> resKm = planKm.calculateRoute(start, end); Pair<Double, List<String>> resHour = planHour.calculateRoute(start, end); Pair<Double, List<String>> resCost = planCost.calculateRoute(start, end); List<String> kmPath = resKm.getValue(); List<String> hourPath = resHour.getValue(); List<String> costPath = resCost.getValue(); // 控制台输出 System.out.println("\n=================================================="); System.out.printf("【%s → %s 规划结果】%n", start, end); System.out.println("=================================================="); if (!kmPath.isEmpty()) { System.out.printf("📏 最短里程：%.0f km | 路线：%s%n", resKm.getKey(), joinPath(kmPath)); } else { System.out.println("📏 最短里程：无可行路线（约束过滤）"); } if (!hourPath.isEmpty()) { System.out.printf("⏰ 最短耗时：%.1f h | 路线：%s%n", resHour.getKey(), joinPath(hourPath)); } else { System.out.println("⏰ 最短耗时：无可行路线（约束过滤）"); } if (!costPath.isEmpty()) { System.out.printf("💰 最低路费：%.0f 元 | 路线：%s%n", resCost.getKey(), joinPath(costPath)); } else { System.out.println("💰 最低路费：无可行路线（约束过滤）"); } System.out.println("=================================================="); try { // 生成图片 if (!kmPath.isEmpty()) { planKm.drawMap("floyd_route_map.png", kmPath); } } catch (Exception e) { e.printStackTrace(); } } }

输出：