# encoding: utf-8
# 版权所有  2026 ©涂聚文有限公司™ ®
# 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎
# 描述：
# 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/7 23:36
# User      :  geovindu
# Product   : PyCharm
# Project   : Pysimple
# File      : Dijkstra demo.py
 
import heapq
import networkx as nx
import matplotlib.pyplot as plt
 
# Dijkstra 通用算法
def dijkstra(graph, start, end):
    dist = {city: float("inf") for city in graph}
    dist[start] = 0
    prev = {city: None for city in graph}
    heap = [(0, start)]
    visited = set()
 
    while heap:
        current_dist, curr_city = heapq.heappop(heap)
        if curr_city in visited:
            continue
        if curr_city == end:
            break
        visited.add(curr_city)
 
        for neighbor, weight in graph[curr_city].items():
            if neighbor in visited:
                continue
            new_dist = current_dist + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = curr_city
                heapq.heappush(heap, (new_dist, neighbor))
 
    # 回溯路径
    path = []
    temp = end
    while temp is not None:
        path.append(temp)
        temp = prev[temp]
    path.reverse()
    return dist[end], path
 
# 路网数据：里程(km)、耗时(h)、高速费(元)
graph_km = {
    "深圳": {"惠州":75, "广州":140, "东莞":65},
    "惠州": {"深圳":75, "河源":90},
    "东莞": {"深圳":65, "广州":50},
    "广州": {"深圳":140, "东莞":50, "韶关":190, "佛山":25},
    "佛山": {"广州":25, "肇庆":70},
    "肇庆": {"佛山":70, "梧州":210},
    "梧州": {"肇庆":210, "桂林":260},
    "桂林": {"梧州":260, "柳州":170},
    "柳州": {"桂林":170, "南宁":220},
    "南宁": {"柳州":220},
    "韶关": {"广州":190, "赣州":230},
    "河源": {"惠州":90, "赣州":180},
    "赣州": {"河源":180, "韶关":230, "吉安":240, "南昌":390},
    "吉安": {"赣州":240, "南昌":215, "萍乡":280},
    "南昌": {"赣州":390, "吉安":215, "九江":130, "福州":380},
    "萍乡": {"吉安":280, "长沙":150},
    "长沙": {"萍乡":150, "武汉":280, "株洲":60},
    "株洲": {"长沙":60, "衡阳":130},
    "衡阳": {"株洲":130, "郴州":180},
    "郴州": {"衡阳":180, "韶关":150},
    "九江": {"南昌":130, "武汉":200},
    "武汉": {"九江":200, "长沙":280, "郑州":470},
    "郑州": {"武汉":470, "西安":450},
    "西安": {"郑州":450},
    "福州": {"南昌":380, "厦门":230},
    "厦门": {"福州":230}
}
 
graph_hour = {
    "深圳": {"惠州":1.0, "广州":1.8, "东莞":0.8},
    "惠州": {"深圳":1.0, "河源":1.3},
    "东莞": {"深圳":0.8, "广州":0.7},
    "广州": {"深圳":1.8, "东莞":0.7, "韶关":2.2, "佛山":0.4},
    "佛山": {"广州":0.4, "肇庆":0.9},
    "肇庆": {"佛山":0.9, "梧州":2.5},
    "梧州": {"肇庆":2.5, "桂林":3.0},
    "桂林": {"梧州":3.0, "柳州":2.0},
    "柳州": {"桂林":2.0, "南宁":2.5},
    "南宁": {"柳州":2.5},
    "韶关": {"广州":2.2, "赣州":2.7},
    "河源": {"惠州":1.3, "赣州":2.0},
    "赣州": {"河源":2.0, "韶关":2.7, "吉安":2.6, "南昌":4.2},
    "吉安": {"赣州":2.6, "南昌":2.3, "萍乡":3.0},
    "南昌": {"赣州":4.2, "吉安":2.3, "九江":1.4, "福州":4.0},
    "萍乡": {"吉安":3.0, "长沙":1.6},
    "长沙": {"萍乡":1.6, "武汉":3.0, "株洲":0.8},
    "株洲": {"长沙":0.8, "衡阳":1.4},
    "衡阳": {"株洲":1.4, "郴州":2.0},
    "郴州": {"衡阳":2.0, "韶关":1.7},
    "九江": {"南昌":1.4, "武汉":2.1},
    "武汉": {"九江":2.1, "长沙":3.0, "郑州":4.8},
    "郑州": {"武汉":4.8, "西安":4.3},
    "西安": {"郑州":4.3},
    "福州": {"南昌":4.0, "厦门":2.4},
    "厦门": {"福州":2.4}
}
 
graph_cost = {
    "深圳": {"惠州":35, "广州":65, "东莞":30},
    "惠州": {"深圳":35, "河源":42},
    "东莞": {"深圳":30, "广州":25},
    "广州": {"深圳":65, "东莞":25, "韶关":85, "佛山":15},
    "佛山": {"广州":15, "肇庆":35},
    "肇庆": {"佛山":35, "梧州":100},
    "梧州": {"肇庆":100, "桂林":120},
    "桂林": {"梧州":120, "柳州":70},
    "柳州": {"桂林":70, "南宁":95},
    "南宁": {"柳州":95},
    "韶关": {"广州":85, "赣州":105},
    "河源": {"惠州":42, "赣州":80},
    "赣州": {"河源":80, "韶关":105, "吉安":110, "南昌":180},
    "吉安": {"赣州":110, "南昌":95, "萍乡":125},
    "南昌": {"赣州":180, "吉安":95, "九江":55, "福州":170},
    "萍乡": {"吉安":125, "长沙":65},
    "长沙": {"萍乡":65, "武汉":130, "株洲":25},
    "株洲": {"长沙":25, "衡阳":55},
    "衡阳": {"株洲":55, "郴州":80},
    "郴州": {"衡阳":80, "韶关":65},
    "九江": {"南昌":55, "武汉":85},
    "武汉": {"九江":85, "长沙":130, "郑州":210},
    "郑州": {"武汉":210, "西安":190},
    "西安": {"郑州":190},
    "福州": {"南昌":170, "厦门":105},
    "厦门": {"福州":105}
}
 
# 城市坐标布局
city_pos = {
    "深圳":(5,0), "惠州":(6,1), "东莞":(4,0), "广州":(3,0),
    "佛山":(2,0), "肇庆":(1,1), "梧州":(-2,2), "桂林":(-3,4),
    "柳州":(-4,3), "南宁":(-5,1), "韶关":(2,4), "河源":(7,3),
    "赣州":(8,6), "吉安":(9,9), "南昌":(10,8), "萍乡":(7,8),
    "长沙":(6,9), "株洲":(6,8), "衡阳":(6,6), "郴州":(6,4),
    "九江":(11,9), "武汉":(9,11), "郑州":(10,14), "西安":(7,15),
    "福州":(13,7), "厦门":(14,4)
}
all_city_list = list(city_pos.keys())
 
def draw_route(start, end, path_km, total_km):
    G = nx.Graph()
    for city, neighbors in graph_km.items():
        for neighbor, km in neighbors.items():
            G.add_edge(city, neighbor, weight=km)
    plt.figure(figsize=(14,11))
    # 全部节点、普通道路
    nx.draw_networkx_nodes(G, city_pos, node_color="#cfe2f3", node_size=1200)
    nx.draw_networkx_edges(G, city_pos, edge_color="#cccccc", width=1)
    nx.draw_networkx_labels(G, city_pos, font_size=9, font_weight="bold")
    # 最优路径红色加粗
    path_edges = list(zip(path_km, path_km[1:]))
    nx.draw_networkx_edges(G, city_pos, edgelist=path_edges, edge_color="red", width=5)
    # 起点终点特殊标记
    nx.draw_networkx_nodes(G, city_pos, nodelist=[start], node_color="#ff7777", node_size=1500)
    nx.draw_networkx_nodes(G, city_pos, nodelist=[end], node_color="#77ff77", node_size=1500)
    # 全部英文标题，无中文，彻底消除警告
    plt.title(f"{start} to {end} Shortest Distance Route | Total: {total_km} km\nPath: {' -> '.join(path_km)}", fontsize=14)
    plt.axis("off")
    plt.tight_layout()
    plt.show()
 
if __name__ == "__main__":
    # Windows专用中文字体配置，微软雅黑系统自带，不会缺失
    plt.rcParams["font.sans-serif"] = ["Microsoft YaHei"]
    plt.rcParams["axes.unicode_minus"] = False
    print("===== China City Highway Route Planner =====")
    print("Available cities:")
    print(", ".join(all_city_list))
    print("-" * 60)
 
    # 交互输入
    while True:
        start_input = input("Input start city: ").strip()
        end_input = input("Input destination city: ").strip()
        # 校验城市是否存在
        if start_input not in all_city_list or end_input not in all_city_list:
            print("City not found, please re-enter!\n")
            continue
        if start_input == end_input:
            print("Start and destination cannot be the same!\n")
            continue
        break
 
    # 计算三种方案
    km_total, km_path = dijkstra(graph_km, start_input, end_input)
    hour_total, hour_path = dijkstra(graph_hour, start_input, end_input)
    cost_total, cost_path = dijkstra(graph_cost, start_input, end_input)
 
    # 控制台输出结果（英文）
    print("\n" + "="*60)
    print(f"【{start_input} -> {end_input} Three Optimal Plans】")
    print("="*60)
    print(f"📏 Shortest Distance: Total {km_total} km")
    print(f"    Route: {' -> '.join(km_path)}")
    print(f"\n⏰ Shortest Time: Total {hour_total:.1f} hours")
    print(f"    Route: {' -> '.join(hour_path)}")
    print(f"\n💰 Minimum Toll Fee: Total {cost_total} RMB")
    print(f"    Route: {' -> '.join(cost_path)}")
    print("="*60)
 
    # 绘制路网图
    draw_route(start_input, end_input, km_path, km_total)
 
 

# encoding: utf-8
# 版权所有  2026 ©涂聚文有限公司™ ®
# 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎
# 描述：Dijkstra 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/9 22:25
# User      :  geovindu
# Product   : PyCharm
# Project   : PyAlgorithms
# File      : Dijkstra.py
import math
import heapq
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):
        self.adj = dict()  # dict[str, dict[str, float]]
 
    def add_edge(self, frm: str, to: str, weight: float):
        if frm not in self.adj:
            self.adj[frm] = dict()
        self.adj[frm][to] = weight
 
        if to not in self.adj:
            self.adj[to] = dict()
        self.adj[to][frm] = weight
 
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 dijkstra(self, start: str, end: str) -> tuple[float, list[str]]:
        INF = float("inf")
        dist = {}
        prev = {}
        visited = set()
 
        # 初始化距离
        for city in self.graph.adj.keys():
            dist[city] = INF
        dist[start] = 0
 
        heap = []
        heapq.heappush(heap, (0.0, start))
 
        while heap:
            curr_dist, curr_city = heapq.heappop(heap)
 
            if curr_city in self.ban_cities or curr_city in visited:
                continue
            if curr_city == end:
                break
            visited.add(curr_city)
 
            # 遍历邻接点
            for neighbor, w in self.graph.adj[curr_city].items():
                if neighbor in self.ban_cities or neighbor in visited:
                    continue
                new_dist = curr_dist + w
                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    prev[neighbor] = curr_city
                    heapq.heappush(heap, (new_dist, neighbor))
 
        # 回溯路径
        path = []
        temp = end
        while temp is not None:
            path.append(temp)
            temp = prev.get(temp, None)
        path.reverse()
 
        # 校验约束
        valid = True
        if len(path) == 0 or path[0] != start:
            valid = False
        else:
            # 必经点校验
            for req in self.must_pass:
                if req not in path:
                    valid = False
                    break
            # 禁行校验
            for node in path:
                if node in self.ban_cities:
                    valid = False
                    break
 
        if not valid:
            return INF, []
        return dist[end], path
 
    def draw_map(self, save_path: str, highlight_route: list[str]):
        # 画布偏移，彻底容纳负X城市（梧州/桂林/柳州/南宁）
        offset_x = 400
        offset_y = 20
        scale = 70
        fig_width = 28
        fig_height = 13
 
        plt.rcParams["font.sans-serif"] = ["Microsoft YaHei"]  # 中文显示
        plt.rcParams["axes.unicode_minus"] = False   # 负号正常显示
        fig, ax = plt.subplots(figsize=(fig_width, fig_height), dpi=100)
        ax.set_title("China City Highway Network | Shortest Path Highlighted", fontsize=14)
        ax.set_xlabel("X Coord")
        ax.set_ylabel("Y Coord")
 
        # 1. 绘制全部普通道路，去重双向边
        drawn_edges = set()
        for frm, neighbors in self.graph.adj.items():
            c_frm = self.city_map[frm]
            fx = c_frm.x * scale + offset_x
            fy = c_frm.y * scale + offset_y
            for to in neighbors.keys():
                key1 = f"{frm}|{to}"
                key2 = f"{to}|{frm}"
                if key1 in drawn_edges or key2 in drawn_edges:
                    continue
                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)
 
        # 2. 绘制高亮最优路径红色粗线
        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
            )
 
        # 3. 绘制城市圆点 + 中文名称
        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():
    # Windows专用中文字体配置，微软雅黑系统自带，不会缺失
    plt.rcParams["font.sans-serif"] = ["Microsoft YaHei"]
    plt.rcParams["axes.unicode_minus"] = False
    # 城市坐标
    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),
    }
 
    # 1. 里程路网 KM
    graph_km = RoadGraph()
    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. 耗时路网 Hour
    graph_hour = RoadGraph()
    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. 路费路网 Cost
    graph_cost = RoadGraph()
    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)
 
    city_list = list(city_data.keys())
    print("===== Python 高速路径规划系统 =====")
    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.dijkstra(start, end)
    hour_total, hour_path = plan_hour.dijkstra(start, end)
    cost_total, cost_path = plan_cost.dijkstra(start, end)
 
    # 输出结果
    print("\n==================================================")
    print(f"【{start} → {end} 规划结果】")
    print("==================================================")
    if km_path:
        print(f"📏 最短里程：{km_total:.0f} km | 路线：{join_path(km_path)}")
    else:
        print("📏 最短里程：无可行路线（约束过滤）")
 
    if hour_path:
        print(f"⏰ 最短耗时：{hour_total:.1f} h | 路线：{join_path(hour_path)}")
    else:
        print("⏰ 最短耗时：无可行路线（约束过滤）")
 
    if cost_path:
        print(f"💰 最低路费：{cost_total:.0f} 元 | 路线：{join_path(cost_path)}")
    else:
        print("💰 最低路费：无可行路线（约束过滤）")
    print("==================================================")
 
    # 输出PNG图片
    if km_path:
        plan_km.draw_map("route_map.png", km_path)
 
if __name__ == "__main__":
    main()
 
 

python: Dijkstra Algorithms

介绍了一个中国城市高速公路路线规划系统，使用Python实现Dijkstra算法计算最优路径。系统提供三种优化方案：最短距离（km）、最短时间（小时）和最低高速费（元），覆盖深圳、广州、南宁、武汉、西安等26个城市。程序通过NetworkX库可视化路线，红色标记最优路径，绿色和红色节点分别标识起点和终点。用户交互界面支持输入起点和目的地城市，输出三种最优方案的详细路径和总成本。该系统采用纯英文输出

编程语言

算法

Python实现Dijkstra算法优化中国高速公路路径规划系统，支持最短里程、耗时和路费三种最优路径计算，包含26个主要城市数据，提供必经点设置和禁行城市功能，可视化展示最优路线图。

Windows

Python

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

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

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

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

社区新版编辑器体验调研

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

python: Dijkstra Algorithms

python: Dijkstra Algorithms

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐