/** * 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 ListString cityNames; public MapString, Integer nameToIdx; private int n; public double[][] distMatrix; public int[][] prevMatrix; public FloydRoadGraph(ListString 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 PairDouble, ListString getPath(String start, String end, SetString 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()); } ListInteger idxPath new ArrayList(); int cur v; while (cur ! -1) { idxPath.add(cur); cur prevMatrix[u][cur]; } Collections.reverse(idxPath); ListString 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 MapString, City cityMap; public ListString mustPassCities new ArrayList(); public SetString banCities new HashSet(); public FloydPathPlanner(FloydRoadGraph graph, MapString, City cityMap) { this.graph graph; this.cityMap cityMap; } // 计算路线校验必经城市 public PairDouble, ListString calculateRoute(String start, String end) { PairDouble, ListString res graph.getPath(start, end, banCities); ListString 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, ListString 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); // 绘制普通道路去重双向边 SetString 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 PairK extends ComparableK, 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(ListString path) { if (path.isEmpty()) return 无路线; return String.join( → , path); } // 解析顿号分隔输入 public static ListString 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 全源最短路径算法示例 ); // 城市坐标数据 MapString, 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)); ListString 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(); ListString mustList parseCityStr(mustInput); ListString 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(); // 计算路线 PairDouble, ListString resKm planKm.calculateRoute(start, end); PairDouble, ListString resHour planHour.calculateRoute(start, end); PairDouble, ListString resCost planCost.calculateRoute(start, end); ListString kmPath resKm.getValue(); ListString hourPath resHour.getValue(); ListString 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(); } } }输出