/* # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 # 描述： Floyd-Warshall 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 : CSharpAlgorithms # File : City.cs */ using System; using System.Collections.Generic; using System.Text; namespace CSharpAlgorithms.FloydWarshal { /// <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 ©涂聚文有限公司™ ® # 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 # 描述： Floyd-Warshall 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 : CSharpAlgorithms # File : FloydRoadGraph.cs */ using System; using System.Collections.Generic; using System.Text; namespace CSharpAlgorithms.FloydWarshal { /// <summary> /// Floyd-Warshall 路网图（距离矩阵+前驱矩阵） /// </summary> public class FloydRoadGraph { private const double INF = double.MaxValue / 2; public List<string> CityNames { get; } public Dictionary<string, int> NameToIdx { get; } private int _n; public double[,] DistMatrix { get; private set; } public int[,] PrevMatrix { get; private set; } /// <summary> /// /// </summary> /// <param name="cityList"></param> public FloydRoadGraph(List<string> cityList) { CityNames = cityList; _n = cityList.Count; NameToIdx = new Dictionary<string, int>(); for (int i = 0; i < _n; i++) NameToIdx[cityList[i]] = i; // 初始化矩阵 DistMatrix = new double[_n, _n]; PrevMatrix = new int[_n, _n]; for (int i = 0; i < _n; i++) { for (int j = 0; j < _n; j++) { DistMatrix[i, j] = INF; PrevMatrix[i, j] = -1; } DistMatrix[i, i] = 0; } } /// <summary> /// 添加双向边 /// </summary> /// <param name="from"></param> /// <param name="to"></param> /// <param name="weight"></param> public void AddEdge(string from, string to, double weight) { int u = NameToIdx[from]; int v = NameToIdx[to]; DistMatrix[u, v] = weight; DistMatrix[v, u] = weight; PrevMatrix[u, v] = u; PrevMatrix[v, u] = v; } /// <summary> /// 执行Floyd-Warshall 全源最短路 /// </summary> public void RunFloyd() { int n = _n; double[,] d = (double[,])DistMatrix.Clone(); int[,] p = (int[,])PrevMatrix.Clone(); for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (d[i, k] + d[k, j] < d[i, j]) { d[i, j] = d[i, k] + d[k, j]; p[i, j] = p[k, j]; } } } } DistMatrix = d; PrevMatrix = p; } /// <summary> /// 回溯路径，过滤禁行城市 /// </summary> /// <param name="start"></param> /// <param name="end"></param> /// <param name="banCities"></param> /// <returns></returns> public (double total, List<string> path) GetPath(string start, string end, HashSet<string> banCities) { if (!NameToIdx.ContainsKey(start) || !NameToIdx.ContainsKey(end)) return (INF, new List<string>()); int u = NameToIdx[start]; int v = NameToIdx[end]; if (DistMatrix[u, v] >= INF) return (INF, new List<string>()); List<int> idxPath = new List<int>(); int curr = v; while (curr != -1) { idxPath.Add(curr); curr = PrevMatrix[u, curr]; } idxPath.Reverse(); List<string> namePath = new List<string>(); foreach (int idx in idxPath) { string city = CityNames[idx]; if (banCities.Contains(city)) return (INF, new List<string>()); namePath.Add(city); } return (DistMatrix[u, v], namePath); } } } using System; using System.Collections.Generic; using System.Drawing; using System.Drawing.Drawing2D; using System.Drawing.Imaging; using System.Text; namespace CSharpAlgorithms.FloydWarshal { /// <summary> /// 路径规划器：约束 + 绘图 /// </summary> public class FloydPathPlanner { private readonly FloydRoadGraph _graph; private readonly Dictionary<string, City> _cityMap; public List<string> MustPassCities = new(); public HashSet<string> BanCities = new(); /// <summary> /// /// </summary> /// <param name="graph"></param> /// <param name="cityMap"></param> public FloydPathPlanner(FloydRoadGraph graph, Dictionary<string, City> cityMap) { _graph = graph; _cityMap = cityMap; } /// <summary> /// /// </summary> /// <param name="start"></param> /// <param name="end"></param> /// <returns></returns> public (double total, List<string> path) CalculateRoute(string start, string end) { var res = _graph.GetPath(start, end, BanCities); double total = res.total; List<string> path = res.path; if (path.Count == 0) return (double.MaxValue, new List<string>()); // 校验必须途经城市 foreach (string req in MustPassCities) { if (!path.Contains(req)) return (double.MaxValue, new List<string>()); } return (total, path); } /// <summary> /// 绘制PNG，偏移充足，负X城市全部可见 /// </summary> /// <param name="savePath"></param> /// <param name="highlightRoute"></param> public void DrawMap(string savePath, List<string> highlightRoute) { int width = 2800; int height = 1300; float offsetX = 400f; float offsetY = 20f; float scale = 70f; float nodeRadius = 8f; using Bitmap bmp = new Bitmap(width, height); using Graphics g = Graphics.FromImage(bmp); g.SmoothingMode = SmoothingMode.AntiAlias; g.Clear(Color.White); // 修复1：FontStyle.Regular 替代不存在的 PLAIN using Font font = new Font("Microsoft YaHei", 11, FontStyle.Regular); using Pen penNormal = new Pen(Color.Gray, 1); using Pen penHighlight = new Pen(Color.Red, 4); using SolidBrush brushNode = new SolidBrush(Color.Blue); using SolidBrush brushText = new SolidBrush(Color.Black); // 绘制普通道路，去重双向边 HashSet<string> drawnEdge = new HashSet<string>(); foreach (string frm in _graph.CityNames) { City cFrom = _cityMap[frm]; float fx = cFrom.X * scale + offsetX; float fy = height - (cFrom.Y * scale + offsetY); foreach (string to in _graph.CityNames) { string k1 = frm + "|" + to; string k2 = to + "|" + frm; if (drawnEdge.Contains(k1) || drawnEdge.Contains(k2)) continue; int u = _graph.NameToIdx[frm]; int v = _graph.NameToIdx[to]; if (_graph.DistMatrix[u, v] >= double.MaxValue / 2) continue; drawnEdge.Add(k1); City cTo = _cityMap[to]; float tx = cTo.X * scale + offsetX; float ty = height - (cTo.Y * scale + offsetY); g.DrawLine(penNormal, 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(penHighlight, ax, ay, bx, by); } // 绘制城市圆点与文字 foreach (City city in _cityMap.Values) { float x = city.X * scale + offsetX; float y = height - (city.Y * scale + offsetY); g.FillEllipse(brushNode, x - nodeRadius, y - nodeRadius, nodeRadius * 2, nodeRadius * 2); g.DrawString(city.Name, font, brushText, x + 4, y - nodeRadius - 14); } // 修复2：原生Image.Save 替代不存在的ImageIO using FileStream fs = new FileStream(savePath, FileMode.Create); bmp.Save(fs, ImageFormat.Png); Console.WriteLine($"✅ 路网图片已保存：{Path.GetFullPath(savePath)}"); } } }

调用：

/* # encoding: utf-8 # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 # 描述： Floyd-Warshall 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 : CSharpAlgorithms # File : FloydWarshallBll.cs */ using CSharpAlgorithms.FloydWarshal; using System; using System.Collections.Generic; using System.Text; namespace CSharpAlgorithms.Bll { /// <summary> /// /// </summary> public class FloydWarshallBll { /// <summary> /// 工具：拼接路径文本 /// </summary> /// <param name="path"></param> /// <returns></returns> public static string JoinPath(List<string> path) { return path.Count == 0 ? "无路线" : string.Join(" → ", path); } /// <summary> /// 工具：解析顿号分隔城市输入 /// </summary> /// <param name="input"></param> /// <returns></returns> public static List<string> ParseCityInput(string input) { if (string.IsNullOrWhiteSpace(input)) return new List<string>(); return input.Split("、", StringSplitOptions.RemoveEmptyEntries) .Select(s => s.Trim()) .Where(s => !string.IsNullOrWhiteSpace(s)) .ToList(); } /// <summary> /// /// </summary> public void Demo() { // 城市坐标数据 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)}, }; List<string> cityList = cityData.Keys.ToList(); #region 1. 里程路网 KM FloydRoadGraph graphKm = new FloydRoadGraph(cityList); 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); graphKm.RunFloyd(); #endregion #region 2. 耗时路网 Hour FloydRoadGraph graphHour = new FloydRoadGraph(cityList); 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); graphHour.RunFloyd(); #endregion #region 3. 路费路网 Cost FloydRoadGraph graphCost = new FloydRoadGraph(cityList); 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); graphCost.RunFloyd(); #endregion // 初始化规划器 FloydPathPlanner planKm = new FloydPathPlanner(graphKm, cityData); FloydPathPlanner planHour = new FloydPathPlanner(graphHour, cityData); FloydPathPlanner planCost = new FloydPathPlanner(graphCost, cityData); Console.WriteLine("===== C# .NET10 Floyd-Warshall 全源路径规划系统 ====="); 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> mustCities = ParseCityInput(mustInput); List<string> banCities = ParseCityInput(banInput); // 统一绑定约束 void SetConstraint(FloydPathPlanner p) { p.MustPassCities = new List<string>(mustCities); p.BanCities = new HashSet<string>(banCities); } SetConstraint(planKm); SetConstraint(planHour); SetConstraint(planCost); // 计算三条路线 var (kmTotal, kmPath) = planKm.CalculateRoute(start, end); var (hourTotal, hourPath) = planHour.CalculateRoute(start, end); var (costTotal, costPath) = planCost.CalculateRoute(start, end); // 控制台输出 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("floyd_route_map.png", kmPath); } } } }

输出：