CSharp: Dijkstra Algorithms

 

/*# encoding: utf-8 
# 版权所有  2026 ©涂聚文有限公司™ ®
# 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎
# 描述：Dijkstra Algorithms
# Author    : geovindu,Geovin Du 涂聚文.
# IDE       : vs2026 c# .net 10
# os        : windows 10
# database  : mysql 9.0 sql server 2019, postgreSQL 17.0  Oracle 21c Neo4j
# Datetime  : 2026/07/04 22:16 
# User      :  geovindu
# Product   : Visual Studio 2026
# Project   : CSharpDesignPattern
# File      : City.cs*/using System;
using System.Collections.Generic;
using System.Text;namespace CSharpAlgorithms.Dijkstra
{// ===================== 数据模型分层 =====================/// <summary>/// 城市坐标实体/// </summary>public class City{public string Name { get; set; }public float X { get; set; }public float Y { get; set; }public City(string name, float x, float y){Name = name;X = x;Y = y;}}
}/*# encoding: utf-8 
# 版权所有  2026 ©涂聚文有限公司™ ®
# 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎
# 描述：Dijkstra Algorithms
# Author    : geovindu,Geovin Du 涂聚文.
# IDE       : vs2026 c# .net 10
# os        : windows 10
# database  : mysql 9.0 sql server 2019, postgreSQL 17.0  Oracle 21c Neo4j
# Datetime  : 2026/07/04 22:16 
# User      :  geovindu
# Product   : Visual Studio 2026
# Project   : CSharpDesignPattern
# File      : RoadGraph.cs*/using System;
using System.Collections.Generic;
using System.Text;namespace CSharpAlgorithms.Dijkstra
{/// <summary>/// 路网邻接图/// </summary>public class RoadGraph{// 邻接表：起点 -> (终点,权重)public Dictionary<string, Dictionary<string, double>> Adj { get; }public RoadGraph(){Adj = new Dictionary<string, Dictionary<string, double>>();}/// <summary>添加双向道路</summary>public void AddEdge(string from, string to, double weight){if (!Adj.ContainsKey(from)) Adj[from] = new Dictionary<string, double>();Adj[from][to] = weight;if (!Adj.ContainsKey(to)) Adj[to] = new Dictionary<string, double>();Adj[to][from] = weight;}}}/*# encoding: utf-8 
# 版权所有  2026 ©涂聚文有限公司™ ®
# 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎
# 描述：Dijkstra Algorithms
# Author    : geovindu,Geovin Du 涂聚文.
# IDE       : vs2026 c# .net 10
# os        : windows 10
# database  : mysql 9.0 sql server 2019, postgreSQL 17.0  Oracle 21c Neo4j
# Datetime  : 2026/07/04 22:16 
# User      :  geovindu
# Product   : Visual Studio 2026
# Project   : CSharpDesignPattern
# File      : PathPlanner.cs*/using System;
using System.Collections.Generic;
using System.Drawing;
using System.Text;
using static System.Net.Mime.MediaTypeNames;
using System.Drawing.Drawing2D;
using System.IO;namespace CSharpAlgorithms.Dijkstra
{/// <summary>/// 路径规划器：承载约束、计算、绘图/// </summary>public class PathPlanner{private readonly RoadGraph _graph;private readonly Dictionary<string, City> _cityMap;// 约束条件public List<string> MustPassCities { get; set; } = new();public HashSet<string> BanCities { get; set; } = new();public PathPlanner(RoadGraph graph, Dictionary<string, City> cityMap){_graph = graph;_cityMap = cityMap;}/// <summary>/// Dijkstra 重构：堆只存城市名，抛弃堆内携带完整路径/// 用前驱表回溯路径，彻底消除元素对比IComparable报错/// </summary>public (double totalWeight, List<string> path) Dijkstra(string start, string end){double INF = double.MaxValue;Dictionary<string, double> dist = new();Dictionary<string, string> prev = new();Dictionary<string, bool> visited = new();// 初始化距离foreach (var city in _graph.Adj.Keys)dist[city] = INF;dist[start] = 0;// 堆：权重double(可比较)，元素仅string城市名，无复杂对象PriorityQueue<double, string> pq = new();pq.Enqueue(0, start);while (pq.Count > 0){pq.TryDequeue(out double currDist, out string currCity);// 跳过禁行、已访问if (BanCities.Contains(currCity) || visited.ContainsKey(currCity))continue;if (currCity == end) break;visited[currCity] = true;// 遍历邻接节点foreach (var (neighbor, w) in _graph.Adj[currCity]){if (BanCities.Contains(neighbor) || visited.ContainsKey(neighbor))continue;double newDist = currDist + w;if (newDist < dist[neighbor]){dist[neighbor] = newDist;prev[neighbor] = currCity;pq.Enqueue(newDist, neighbor);}}}// 回溯完整路径List<string> fullPath = new List<string>();string temp = end;while (!string.IsNullOrEmpty(temp)){fullPath.Add(temp);temp = prev.ContainsKey(temp) ? prev[temp] : null;}fullPath.Reverse();// 校验路径合法性：起点正确、包含所有必经城市、无禁行bool pathValid = fullPath.Count > 0 && fullPath[0] == start;if (pathValid){foreach (var reqCity in MustPassCities){if (!fullPath.Contains(reqCity)){pathValid = false;break;}}foreach (var node in fullPath){if (BanCities.Contains(node)){pathValid = false;break;}}}if (!pathValid)return (INF, new List<string>());return (dist[end], fullPath);}/// <summary>/// 绘制路网PNG，带中文城市名称、高亮最优路径/// </summary>public void DrawMap(string savePath, List<string> highlightRoute, int width = 2800, int height = 1300){// 超大X偏移，容纳 X=-5 南宁：-5*70 = -350，加400后变为正数float offsetX = 400f;float offsetY = 20f;float scale = 70f;using Bitmap bmp = new Bitmap(width, height);using Graphics g = Graphics.FromImage(bmp);g.Clear(Color.White);g.SmoothingMode = SmoothingMode.AntiAlias;using System.Drawing.Font fontCity = new System.Drawing.Font("Microsoft YaHei", 11);using Pen penRoadNormal = new Pen(Color.Gray, 1);using Pen penRoadHighlight = new Pen(Color.Red, 4);using SolidBrush brushCityNode = new SolidBrush(Color.Blue);using SolidBrush brushText = new SolidBrush(Color.Black);// 绘制所有普通道路HashSet<Tuple<string, string>> drawnEdge = new();foreach (var (from, neighbors) in _graph.Adj){City cFrom = _cityMap[from];float fx = cFrom.X * scale + offsetX;float fy = height - (cFrom.Y * scale + offsetY);foreach (var to in neighbors.Keys){var edgeKey = string.Compare(from, to) < 0? Tuple.Create(from, to): Tuple.Create(to, from);if (drawnEdge.Contains(edgeKey)) continue;drawnEdge.Add(edgeKey);City cTo = _cityMap[to];float tx = cTo.X * scale + offsetX;float ty = height - (cTo.Y * scale + offsetY);g.DrawLine(penRoadNormal, fx, fy, tx, ty);}}// 绘制高亮最优路径for (int i = 0; i < highlightRoute.Count - 1; i++){string a = highlightRoute[i];string b = highlightRoute[i + 1];City ca = _cityMap[a];City cb = _cityMap[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);g.DrawLine(penRoadHighlight, ax, ay, bx, by);}// 绘制所有城市圆点+文字（包含负X西部城市）foreach (var city in _cityMap.Values){float x = city.X * scale + offsetX;float y = height - (city.Y * scale + offsetY);float radius = 8;g.FillEllipse(brushCityNode, x - radius, y - radius, radius * 2, radius * 2);g.DrawString(city.Name, fontCity, brushText, x + 4, y - radius - 14);}bmp.Save(savePath, System.Drawing.Imaging.ImageFormat.Png);Console.WriteLine($"路网图片已保存：{Path.GetFullPath(savePath)}");}}}/*# encoding: utf-8 
# 版权所有  2026 ©涂聚文有限公司™ ®
# 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎
# 描述：Dijkstra Algorithms
# Author    : geovindu,Geovin Du 涂聚文.
# IDE       : vs2026 c# .net 10
# os        : windows 10
# database  : mysql 9.0 sql server 2019, postgreSQL 17.0  Oracle 21c Neo4j
# Datetime  : 2026/07/04 22:16 
# User      :  geovindu
# Product   : Visual Studio 2026
# Project   : CSharpDesignPattern
# File      : Program.cs*/using CSharpAlgorithms.Dijkstra;namespace CSharpAlgorithms
{internal class Program{static void Main(string[] args){// 1. 城市坐标定义Dictionary<string, City> cityData = new(){{"深圳", new City("深圳", 5, 0)},{"惠州", new City("惠州", 6, 1)},{"东莞", new City("东莞", 4, 0)},{"广州", new City("广州", 3, 0)},{"佛山", new City("佛山", 2, 0)},{"肇庆", new City("肇庆", 1, 1)},{"梧州", new City("梧州", -2, 2)},{"桂林", new City("桂林", -3, 4)},{"柳州", new City("柳州", -4, 3)},{"南宁", new City("南宁", -5, 1)},{"韶关", new City("韶关", 2, 4)},{"河源", new City("河源", 7, 3)},{"赣州", new City("赣州", 8, 6)},{"吉安", new City("吉安", 9, 9)},{"南昌", new City("南昌", 10, 8)},{"萍乡", new City("萍乡", 7, 8)},{"长沙", new City("长沙", 6, 9)},{"株洲", new City("株洲", 6, 8)},{"衡阳", new City("衡阳", 6, 6)},{"郴州", new City("郴州", 6, 4)},{"九江", new City("九江", 11, 9)},{"武汉", new City("武汉", 9, 11)},{"郑州", new City("郑州", 10, 14)},{"西安", new City("西安", 7, 15)},{"福州", new City("福州", 13, 7)},{"厦门", new City("厦门", 14, 4)},};// 2. 构建三类路网// 里程路网 KMRoadGraph graphKm = new();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);// 耗时路网 HourRoadGraph graphHour = new();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);// 路费路网 CostRoadGraph graphCost = new();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);// 打印城市列表var cityList = cityData.Keys.ToList();Console.WriteLine("===== C# .NET10 高速路径规划系统 =====");Console.WriteLine($"可用城市：{string.Join("、", cityList)}");Console.WriteLine("----------------------------------------");// 交互输入Console.Write("输入起点城市：");string start = Console.ReadLine()?.Trim() ?? "";Console.Write("输入终点城市：");string end = Console.ReadLine()?.Trim() ?? "";Console.Write("必须途经城市（多城顿号分隔，无直接回车）：");string mustInput = Console.ReadLine()?.Trim() ?? "";Console.Write("禁止绕行城市（多城顿号分隔，无直接回车）：");string banInput = Console.ReadLine()?.Trim() ?? "";// 解析约束List<string> ParseCityStr(string s){if (string.IsNullOrEmpty(s)) return new();return s.Split("、", StringSplitOptions.RemoveEmptyEntries).Select(x => x.Trim()).ToList();}var mustCities = ParseCityStr(mustInput);var banCities = ParseCityStr(banInput);// 绑定约束到三个规划器void SetConstraint(PathPlanner p){p.MustPassCities = new List<string>(mustCities);p.BanCities = new HashSet<string>(banCities);}SetConstraint(planKm);SetConstraint(planHour);SetConstraint(planCost);// 计算路线var (kmTotal, kmPath) = planKm.Dijkstra(start, end);var (hourTotal, hourPath) = planHour.Dijkstra(start, end);var (costTotal, costPath) = planCost.Dijkstra(start, end);// 拼接路径文本string JoinPath(List<string> path) => path.Count == 0 ? "无路线" : string.Join(" → ", path);// 输出结果Console.WriteLine("\n==================================================");Console.WriteLine($"【{start} → {end} 规划结果】");Console.WriteLine("==================================================");Console.WriteLine(kmPath.Count > 0? $"📏 最短里程：{kmTotal:F0} km | 路线：{JoinPath(kmPath)}": "📏 最短里程：无可行路线（约束过滤）");Console.WriteLine(hourPath.Count > 0? $"⏰ 最短耗时：{hourTotal:F1} h | 路线：{JoinPath(hourPath)}": "⏰ 最短耗时：无可行路线（约束过滤）");Console.WriteLine(costPath.Count > 0? $"💰 最低路费：{costTotal:F0} 元 | 路线：{JoinPath(costPath)}": "💰 最低路费：无可行路线（约束过滤）");Console.WriteLine("==================================================");// 绘制PNG图（里程最优路线）if (kmPath.Count > 0){planKm.DrawMap("route_map.png", kmPath);}}}
}

　　

输出：