java: Dijkstra Algorithms

介绍了一个基于Dijkstra算法的Java路径规划系统。系统包含三个主要类City类存储城市坐标信息RoadGraph类实现路网邻接表PathPlanner类提供路径规划功能支持最短里程/耗时/路费三种优化目标必经城市和禁行城市约束路径可视化生成PNG图片系统提供交互式控制台界面用户可输入起点、终点及约束条件。示例数据包含中国30个城市的路网信息里程、耗时、路费三种权重。程序输出最优路径并生成可视化路网图其中最优路径以红色高亮显示。代码采用Java 17编写使用优先队列实现Dijkstra算法时间复杂度为O(ElogV)。/** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 Dijkstra 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/9 - 22:55 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : City.java * explain : 学习 类 **/ package Dijkstra; /** * 城市坐标实体 * */ 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 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 Dijkstra 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/9 - 22:56 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : RoadGraph.java * explain : 学习 类 **/ package Dijkstra; import javax.imageio.ImageIO; import java.awt.*; import java.awt.image.BufferedImage; import java.io.File; import java.util.*; import java.util.List; import java.util.stream.Collectors; /** * 路网邻接表 * */ public class RoadGraph { public MapString, MapString, Double adj new HashMap(); // 添加双向道路 public void addEdge(String from, String to, double weight) { adj.computeIfAbsent(from, k - new HashMap()).put(to, weight); adj.computeIfAbsent(to, k - new HashMap()).put(from, weight); } } /** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 Dijkstra 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/9 - 22:57 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : Pair.java * explain : 学习 类 **/ package Dijkstra; /** * 路网邻接表 * */ 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 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 Dijkstra 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/9 - 22:58 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : PathPlanner.java * explain : 学习 类 **/ package Dijkstra; import javax.imageio.ImageIO; import java.awt.*; import java.awt.image.BufferedImage; import java.io.File; import java.util.*; import java.util.List; import java.util.stream.Collectors; /** *路径规划器Dijkstra算法 绘图生成PNG * */ public class PathPlanner { private final RoadGraph graph; private final MapString, City cityMap; // 约束条件 public ListString mustPassCities new ArrayList(); public SetString banCities new HashSet(); public PathPlanner(RoadGraph graph, MapString, City cityMap) { this.graph graph; this.cityMap cityMap; } /** * Dijkstra 算法队列仅存城市字符串无比较异常 */ public PairDouble, ListString dijkstra(String start, String end) { double INF Double.MAX_VALUE; MapString, Double dist new HashMap(); MapString, String prev new HashMap(); SetString visited new HashSet(); // 初始化距离为无穷大 for (String city : graph.adj.keySet()) { dist.put(city, INF); } dist.put(start, 0.0); // 最小堆权重城市名 PriorityQueuePairDouble, String pq new PriorityQueue(Comparator.comparing(Pair::getKey)); pq.add(new Pair(0.0, start)); while (!pq.isEmpty()) { PairDouble, String curr pq.poll(); double currDist curr.getKey(); String currCity curr.getValue(); // 跳过禁行/已访问城市 if (banCities.contains(currCity) || visited.contains(currCity)) { continue; } if (currCity.equals(end)) { break; } visited.add(currCity); // 遍历邻接道路 MapString, Double neighbors graph.adj.get(currCity); for (Map.EntryString, Double entry : neighbors.entrySet()) { String neighbor entry.getKey(); double w entry.getValue(); if (banCities.contains(neighbor) || visited.contains(neighbor)) { continue; } double newDist currDist w; if (newDist dist.get(neighbor)) { dist.put(neighbor, newDist); prev.put(neighbor, currCity); pq.add(new Pair(newDist, neighbor)); } } } // 反向回溯路径 ListString fullPath new ArrayList(); String temp end; while (temp ! null) { fullPath.add(temp); temp prev.get(temp); } Collections.reverse(fullPath); // 校验路径合法性起点、必经城市、禁行城市 boolean valid true; if (fullPath.isEmpty() || !fullPath.get(0).equals(start)) { valid false; } else { // 校验必经点 for (String req : mustPassCities) { if (!fullPath.contains(req)) { valid false; break; } } // 校验禁行城市 for (String node : fullPath) { if (banCities.contains(node)) { valid false; break; } } } if (!valid) { return new Pair(INF, new ArrayList()); } return new Pair(dist.get(end), fullPath); } /** * 绘制路网PNG */ 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); Font font new Font(Microsoft YaHei, Font.PLAIN, 11); g2d.setFont(font); // 1. 绘制全部普通灰色道路去重双向边 SetString edgeRecord new HashSet(); for (Map.EntryString, MapString, Double entry : graph.adj.entrySet()) { String fromName entry.getKey(); City fromCity cityMap.get(fromName); float fx fromCity.x * scale offsetX; float fy height - (fromCity.y * scale offsetY); for (String toName : entry.getValue().keySet()) { String key1 fromName | toName; String key2 toName | fromName; if (edgeRecord.contains(key1) || edgeRecord.contains(key2)) { continue; } edgeRecord.add(key1); City toCity cityMap.get(toName); float tx toCity.x * scale offsetX; float ty height - (toCity.y * scale offsetY); g2d.setColor(Color.GRAY); g2d.setStroke(new BasicStroke(1)); g2d.drawLine((int) fx, (int) fy, (int) tx, (int) ty); } } // 2. 绘制红色高亮最优路径 g2d.setColor(Color.RED); g2d.setStroke(new BasicStroke(4)); 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); } // 3. 绘制蓝色圆点 城市中文名称 for (City city : cityMap.values()) { float x city.x * scale offsetX; float y height - (city.y * scale offsetY); g2d.setColor(Color.BLUE); int cx (int) (x - nodeRadius); int cy (int) (y - nodeRadius); int cr (int) (nodeRadius * 2); g2d.fillOval(cx, cy, cr, cr); g2d.setColor(Color.BLACK); g2d.drawString(city.name, (int) (x 4), (int) (y - nodeRadius - 14)); } g2d.dispose(); ImageIO.write(image, png, new File(savePath)); System.out.println(路网图片已生成 new File(savePath).getAbsolutePath()); } }调用/** * encoding: utf-8 * 版权所有 2026 ©涂聚文有限公司 ® * 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 * 描述 Dijkstra 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/9 - 22:55 * User : geovindu * Product : IntelliJ IDEA * Project : JavaAlgorithms * File : Main.java * explain : 学习 类 **/ import Dijkstra.*; import javax.imageio.ImageIO; import java.awt.*; import java.awt.image.BufferedImage; import java.io.File; import java.util.*; import java.util.List; import java.util.stream.Collectors; public class Main { // 【修复1】解析城市输入字符串 静态方法放在类内部 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()); } // 【修复2】路径拼接工具 静态方法放在类内部 public static String joinPath(ListString path) { if (path null || path.isEmpty()) { return 无路线; } return String.join( → , path); } public static void main(String[] args) { // 城市坐标定义含负X西部城市梧州、桂林、柳州、南宁 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)); // 1. 里程路网 KM RoadGraph graphKm new RoadGraph(); 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); // 2. 耗时路网 Hour RoadGraph graphHour new RoadGraph(); 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); // 3. 路费路网 Cost RoadGraph graphCost new RoadGraph(); 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); // 初始化三个规划器 PathPlanner planKm new PathPlanner(graphKm, cityData); PathPlanner planHour new PathPlanner(graphHour, cityData); PathPlanner planCost new PathPlanner(graphCost, cityData); // 打印所有城市列表 ListString cityList new ArrayList(cityData.keySet()); System.out.println( Java JDK17 高速路径规划系统 ); System.out.println(可用城市 String.join(、, cityList)); System.out.println(----------------------------------------); // 控制台交互输入 Scanner scanner new Scanner(System.in); System.out.print(输入起点城市); String start scanner.nextLine().trim(); System.out.print(输入终点城市); String end scanner.nextLine().trim(); System.out.print(必须途经城市多城顿号分隔无则直接回车); String mustInput scanner.nextLine().trim(); System.out.print(禁止绕行城市多城顿号分隔无则直接回车); String banInput scanner.nextLine().trim(); scanner.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(); // 执行Dijkstra计算三条路线 PairDouble, ListString resKm planKm.dijkstra(start, end); PairDouble, ListString resHour planHour.dijkstra(start, end); PairDouble, ListString resCost planCost.dijkstra(start, end); // 控制台输出结果 System.out.println(\n); System.out.printf(【%s → %s 规划结果】%n, start, end); System.out.println(); if (!resKm.getValue().isEmpty()) { System.out.printf( 最短里程%.0f km | 路线%s%n, resKm.getKey(), joinPath(resKm.getValue())); } else { System.out.println( 最短里程无可行路线约束过滤); } if (!resHour.getValue().isEmpty()) { System.out.printf(⏰ 最短耗时%.1f h | 路线%s%n, resHour.getKey(), joinPath(resHour.getValue())); } else { System.out.println(⏰ 最短耗时无可行路线约束过滤); } if (!resCost.getValue().isEmpty()) { System.out.printf( 最低路费%.0f 元 | 路线%s%n, resCost.getKey(), joinPath(resCost.getValue())); } else { System.out.println( 最低路费无可行路线约束过滤); } System.out.println(); // 生成PNG路网图里程最优路线 if (!resKm.getValue().isEmpty()) { try { planKm.drawMap(route_map.png, resKm.getValue()); } catch (Exception e) { System.err.println(❌ 生成路网图片失败 e.getMessage()); e.printStackTrace(); } } System.out.println(Hello, World!); } }输出