# encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Floyd-Warshall Algorithms全源最短路径算法 # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2024.3.6 python 3.11 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/10 23:03 # User : geovindu # Product : PyCharm # Project : PyAlgorithms # File : FloydWarshall.py import math import matplotlib.pyplot as plt # 数据模型 class City: def __init__(self, name: str, x: float, y: float): self.name name self.x x self.y y class RoadGraph: def __init__(self, city_names: list[str]): self.city_names city_names self.n len(city_names) self.name2idx {name:i for i,name in enumerate(city_names)} self.INF float(inf) # 初始化距离矩阵 self.dist [[self.INF]*self.n for _ in range(self.n)] for i in range(self.n): self.dist[i][i] 0 def add_edge(self, frm: str, to: str, weight: float): u self.name2idx[frm] v self.name2idx[to] self.dist[u][v] weight self.dist[v][u] weight # Floyd-Warshall 计算全源最短路 def floyd(self): d [row[:] for row in self.dist] n self.n for k in range(n): for i in range(n): for j in range(n): if d[i][k] d[k][j] d[i][j]: d[i][j] d[i][k] d[k][j] self.full_dist d # 根据起点终点回溯路径 def get_path(self, start: str, end: str, ban_set: set[str]): # 先构建前驱矩阵改造Floyd时记录前驱这里重新回溯 n self.n prev [[-1]*n for _ in range(n)] # 重新初始化前驱 for i in range(n): for j in range(n): if self.dist[i][j] ! self.INF and i ! j: prev[i][j] i # Floyd更新前驱 d [row[:] for row in self.dist] for k in range(n): for i in range(n): for j in range(n): if d[i][k] d[k][j] d[i][j]: d[i][j] d[i][k] d[k][j] prev[i][j] prev[k][j] self.full_dist d u self.name2idx[start] v self.name2idx[end] if d[u][v] self.INF: return self.INF, [] # 回溯路径 path_idx [] curr v while curr ! -1: path_idx.append(curr) curr prev[u][curr] path_idx.reverse() path [self.city_names[i] for i in path_idx] # 过滤禁行城市 for node in path: if node in ban_set: return self.INF, [] return d[u][v], path class PathPlanner: def __init__(self, graph: RoadGraph, city_map: dict[str, City]): self.graph graph self.city_map city_map self.must_pass [] self.ban_cities set() def set_must_pass(self, city_list: list[str]): self.must_pass city_list def add_ban_city(self, city: str): self.ban_cities.add(city) def clear_ban(self): self.ban_cities.clear() def calc_route(self, start: str, end: str) - tuple[float, list[str]]: total, path self.graph.get_path(start, end, self.ban_cities) if not path: return total, [] # 校验必经城市 for req in self.must_pass: if req not in path: return float(inf), [] return total, path def draw_map(self, save_path: str, highlight_route: list[str]): offset_x 400 offset_y 20 scale 70 fig_width 28 fig_height 13 # 兼容多系统中文字体 plt.rcParams[font.sans-serif] [Microsoft YaHei, SimHei, PingFang SC] plt.rcParams[axes.unicode_minus] False fig, ax plt.subplots(figsize(fig_width, fig_height), dpi100) ax.set_title(City Highway Network | Floyd-Warshall Shortest Path, fontsize14) drawn_edges set() for frm in self.graph.city_names: c_frm self.city_map[frm] fx c_frm.x * scale offset_x fy c_frm.y * scale offset_y for to in self.graph.city_names: if frm to: continue key1 f{frm}|{to} key2 f{to}|{frm} if key1 in drawn_edges or key2 in drawn_edges: continue if self.graph.dist[self.graph.name2idx[frm]][self.graph.name2idx[to]] ! float(inf): drawn_edges.add(key1) c_to self.city_map[to] tx c_to.x * scale offset_x ty c_to.y * scale offset_y ax.plot([fx, tx], [fy, ty], color#888888, linewidth1) # 高亮路径 for i in range(len(highlight_route)-1): a highlight_route[i] b highlight_route[i1] ca self.city_map[a] cb self.city_map[b] ax.plot( [ca.x*scaleoffset_x, cb.x*scaleoffset_x], [ca.y*scaleoffset_y, cb.y*scaleoffset_y], colorred, linewidth4 ) # 绘制城市文字圆点 for city in self.city_map.values(): x city.x * scale offset_x y city.y * scale offset_y ax.scatter(x, y, colorblue, s120, zorder5) ax.text(x 0.12, y 0.22, city.name, fontsize11, colorblack, zorder6) plt.tight_layout() plt.savefig(save_path, bbox_inchestight) plt.close() print(f路网图片已保存{save_path}) # 工具函数 def join_path(path: list[str]) - str: if len(path) 0: return 无路线 return → .join(path) def parse_city_input(s: str) - list[str]: if not s.strip(): return [] return [x.strip() for x in s.split(、) if x.strip()] # 主程序 def main(): city_data { 深圳: City(深圳, 5, 0), 惠州: City(惠州, 6, 1), 东莞: City(东莞, 4, 0), 广州: City(广州, 3, 0), 佛山: City(佛山, 2, 0), 肇庆: City(肇庆, 1, 1), 梧州: City(梧州, -2, 2), 桂林: City(桂林, -3, 4), 柳州: City(柳州, -4, 3), 南宁: City(南宁, -5, 1), 韶关: City(韶关, 2, 4), 河源: City(河源, 7, 3), 赣州: City(赣州, 8, 6), 吉安: City(吉安, 9, 9), 南昌: City(南昌, 10, 8), 萍乡: City(萍乡, 7, 8), 长沙: City(长沙, 6, 9), 株洲: City(株洲, 6, 8), 衡阳: City(衡阳, 6, 6), 郴州: City(郴州, 6, 4), 九江: City(九江, 11, 9), 武汉: City(武汉, 9, 11), 郑州: City(郑州, 10, 14), 西安: City(西安, 7, 15), 福州: City(福州, 13, 7), 厦门: City(厦门, 14, 4), } city_list list(city_data.keys()) # 1. 里程路网 graph_km RoadGraph(city_list) graph_km.add_edge(深圳, 惠州, 75) graph_km.add_edge(深圳, 广州, 140) graph_km.add_edge(深圳, 东莞, 65) graph_km.add_edge(惠州, 河源, 90) graph_km.add_edge(东莞, 广州, 50) graph_km.add_edge(广州, 韶关, 190) graph_km.add_edge(广州, 佛山, 25) graph_km.add_edge(佛山, 肇庆, 70) graph_km.add_edge(肇庆, 梧州, 210) graph_km.add_edge(梧州, 桂林, 260) graph_km.add_edge(桂林, 柳州, 170) graph_km.add_edge(柳州, 南宁, 220) graph_km.add_edge(韶关, 赣州, 230) graph_km.add_edge(河源, 赣州, 180) graph_km.add_edge(赣州, 吉安, 240) graph_km.add_edge(赣州, 南昌, 390) graph_km.add_edge(吉安, 南昌, 215) graph_km.add_edge(吉安, 萍乡, 280) graph_km.add_edge(萍乡, 长沙, 150) graph_km.add_edge(长沙, 武汉, 280) graph_km.add_edge(长沙, 株洲, 60) graph_km.add_edge(株洲, 衡阳, 130) graph_km.add_edge(衡阳, 郴州, 180) graph_km.add_edge(郴州, 韶关, 150) graph_km.add_edge(南昌, 九江, 130) graph_km.add_edge(九江, 武汉, 200) graph_km.add_edge(武汉, 郑州, 470) graph_km.add_edge(郑州, 西安, 450) graph_km.add_edge(南昌, 福州, 380) graph_km.add_edge(福州, 厦门, 230) # 2. 耗时路网 graph_hour RoadGraph(city_list) graph_hour.add_edge(深圳, 惠州, 1.0) graph_hour.add_edge(深圳, 广州, 1.8) graph_hour.add_edge(深圳, 东莞, 0.8) graph_hour.add_edge(惠州, 河源, 1.3) graph_hour.add_edge(东莞, 广州, 0.7) graph_hour.add_edge(广州, 韶关, 2.2) graph_hour.add_edge(广州, 佛山, 0.4) graph_hour.add_edge(佛山, 肇庆, 0.9) graph_hour.add_edge(肇庆, 梧州, 2.5) graph_hour.add_edge(梧州, 桂林, 3.0) graph_hour.add_edge(桂林, 柳州, 2.0) graph_hour.add_edge(柳州, 南宁, 2.5) graph_hour.add_edge(韶关, 赣州, 2.7) graph_hour.add_edge(河源, 赣州, 2.0) graph_hour.add_edge(赣州, 吉安, 2.6) graph_hour.add_edge(赣州, 南昌, 4.2) graph_hour.add_edge(吉安, 南昌, 2.3) graph_hour.add_edge(吉安, 萍乡, 3.0) graph_hour.add_edge(萍乡, 长沙, 1.6) graph_hour.add_edge(长沙, 武汉, 3.0) graph_hour.add_edge(长沙, 株洲, 0.8) graph_hour.add_edge(株洲, 衡阳, 1.4) graph_hour.add_edge(衡阳, 郴州, 2.0) graph_hour.add_edge(郴州, 韶关, 1.7) graph_hour.add_edge(南昌, 九江, 1.4) graph_hour.add_edge(九江, 武汉, 2.1) graph_hour.add_edge(武汉, 郑州, 4.8) graph_hour.add_edge(郑州, 西安, 4.3) graph_hour.add_edge(南昌, 福州, 4.0) graph_hour.add_edge(福州, 厦门, 2.4) # 3. 路费路网 graph_cost RoadGraph(city_list) graph_cost.add_edge(深圳, 惠州, 35) graph_cost.add_edge(深圳, 广州, 65) graph_cost.add_edge(深圳, 东莞, 30) graph_cost.add_edge(惠州, 河源, 42) graph_cost.add_edge(东莞, 广州, 25) graph_cost.add_edge(广州, 韶关, 85) graph_cost.add_edge(广州, 佛山, 15) graph_cost.add_edge(佛山, 肇庆, 35) graph_cost.add_edge(肇庆, 梧州, 100) graph_cost.add_edge(梧州, 桂林, 120) graph_cost.add_edge(桂林, 柳州, 70) graph_cost.add_edge(柳州, 南宁, 95) graph_cost.add_edge(韶关, 赣州, 105) graph_cost.add_edge(河源, 赣州, 80) graph_cost.add_edge(赣州, 吉安, 110) graph_cost.add_edge(赣州, 南昌, 180) graph_cost.add_edge(吉安, 南昌, 95) graph_cost.add_edge(吉安, 萍乡, 125) graph_cost.add_edge(萍乡, 长沙, 65) graph_cost.add_edge(长沙, 武汉, 130) graph_cost.add_edge(长沙, 株洲, 25) graph_cost.add_edge(株洲, 衡阳, 55) graph_cost.add_edge(衡阳, 郴州, 80) graph_cost.add_edge(郴州, 韶关, 65) graph_cost.add_edge(南昌, 九江, 55) graph_cost.add_edge(九江, 武汉, 85) graph_cost.add_edge(武汉, 郑州, 210) graph_cost.add_edge(郑州, 西安, 190) graph_cost.add_edge(南昌, 福州, 170) graph_cost.add_edge(福州, 厦门, 105) plan_km PathPlanner(graph_km, city_data) plan_hour PathPlanner(graph_hour, city_data) plan_cost PathPlanner(graph_cost, city_data) print( Python Floyd-Warshall 全源路径规划系统 ) print(f可用城市{、.join(city_list)}) print(----------------------------------------) start input(输入起点城市).strip() end input(输入终点城市).strip() must_input input(必须途经城市多城顿号分隔无直接回车).strip() ban_input input(禁止绕行城市多城顿号分隔无直接回车).strip() must_list parse_city_input(must_input) ban_list parse_city_input(ban_input) def set_constraint(planner: PathPlanner): planner.set_must_pass(must_list) planner.clear_ban() for c in ban_list: planner.add_ban_city(c) set_constraint(plan_km) set_constraint(plan_hour) set_constraint(plan_cost) km_total, km_path plan_km.calc_route(start, end) hour_total, hour_path plan_hour.calc_route(start, end) cost_total, cost_path plan_cost.calc_route(start, end) print(\n) print(f【{start} → {end} 规划结果】) print() print(f 最短里程{km_total:.0f} km | 路线{join_path(km_path)} if km_path else 最短里程无可行路线约束过滤) print(f⏰ 最短耗时{hour_total:.1f} h | 路线{join_path(hour_path)} if hour_path else ⏰ 最短耗时无可行路线约束过滤) print(f 最低路费{cost_total:.0f} 元 | 路线{join_path(cost_path)} if cost_path else 最低路费无可行路线约束过滤) print() if km_path: plan_km.draw_map(floyd_route_map.png, km_path) if __name__ __main__: main()输出