# 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), dpi=100)
        ax.set_title("City Highway Network | Floyd-Warshall Shortest Path", fontsize=14)
 
        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", linewidth=1)
 
        # 高亮路径
        for i in range(len(highlight_route)-1):
            a = highlight_route[i]
            b = highlight_route[i+1]
            ca = self.city_map[a]
            cb = self.city_map[b]
            ax.plot(
                [ca.x*scale+offset_x, cb.x*scale+offset_x],
                [ca.y*scale+offset_y, cb.y*scale+offset_y],
                color="red", linewidth=4
            )
 
        # 绘制城市文字圆点
        for city in self.city_map.values():
            x = city.x * scale + offset_x
            y = city.y * scale + offset_y
            ax.scatter(x, y, color="blue", s=120, zorder=5)
            ax.text(x + 0.12, y + 0.22, city.name, fontsize=11, color="black", zorder=6)
 
        plt.tight_layout()
        plt.savefig(save_path, bbox_inches="tight")
        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()
 
 
 

python:Floyd-Warshall Algorithms

一个基于Floyd-Warshall算法的全源最短路径规划系统。该系统实现了三种不同指标的路径规划（里程、耗时、路费），支持起点/终点设置、必经城市和禁行城市约束。系统通过构建城市路网图，采用Floyd算法计算全源最短路径，并提供了路径可视化功能。测试数据包含26个城市及其连接关系，用户可交互式输入参数获取最优路线。结果显示时同时输出三种指标下的最优路径及对应数值，满足不同场景的路径规划需求。

编程语言

算法

Python实现Floyd-Warshall全源最短路径算法，支持城市路网规划，计算最短里程、耗时和路费。提供必经城市设置和禁行城市过滤功能，可视化展示最优路线图，适用于交通导航和物流路径优化。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

python:Floyd-Warshall Algorithms-腾讯云开发者社区-腾讯云

python:Floyd-Warshall Algorithms

python:Floyd-Warshall Algorithms

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐