CSharp: Floyd-Warshall Algorithms

/* # 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 Liststring CityNames { get; } public Dictionarystring, int NameToIdx { get; } private int _n; public double[,] DistMatrix { get; private set; } public int[,] PrevMatrix { get; private set; } /// summary /// /// /summary /// param namecityList/param public FloydRoadGraph(Liststring cityList) { CityNames cityList; _n cityList.Count; NameToIdx new Dictionarystring, 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 namefrom/param /// param nameto/param /// param nameweight/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 namestart/param /// param nameend/param /// param namebanCities/param /// returns/returns public (double total, Liststring path) GetPath(string start, string end, HashSetstring banCities) { if (!NameToIdx.ContainsKey(start) || !NameToIdx.ContainsKey(end)) return (INF, new Liststring()); int u NameToIdx[start]; int v NameToIdx[end]; if (DistMatrix[u, v] INF) return (INF, new Liststring()); Listint idxPath new Listint(); int curr v; while (curr ! -1) { idxPath.Add(curr); curr PrevMatrix[u, curr]; } idxPath.Reverse(); Liststring namePath new Liststring(); foreach (int idx in idxPath) { string city CityNames[idx]; if (banCities.Contains(city)) return (INF, new Liststring()); 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 Dictionarystring, City _cityMap; public Liststring MustPassCities new(); public HashSetstring BanCities new(); /// summary /// /// /summary /// param namegraph/param /// param namecityMap/param public FloydPathPlanner(FloydRoadGraph graph, Dictionarystring, City cityMap) { _graph graph; _cityMap cityMap; } /// summary /// /// /summary /// param namestart/param /// param nameend/param /// returns/returns public (double total, Liststring path) CalculateRoute(string start, string end) { var res _graph.GetPath(start, end, BanCities); double total res.total; Liststring path res.path; if (path.Count 0) return (double.MaxValue, new Liststring()); // 校验必须途经城市 foreach (string req in MustPassCities) { if (!path.Contains(req)) return (double.MaxValue, new Liststring()); } return (total, path); } /// summary /// 绘制PNG偏移充足负X城市全部可见 /// /summary /// param namesavePath/param /// param namehighlightRoute/param public void DrawMap(string savePath, Liststring 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); // 修复1FontStyle.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); // 绘制普通道路去重双向边 HashSetstring drawnEdge new HashSetstring(); 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 namepath/param /// returns/returns public static string JoinPath(Liststring path) { return path.Count 0 ? 无路线 : string.Join( → , path); } /// summary /// 工具解析顿号分隔城市输入 /// /summary /// param nameinput/param /// returns/returns public static Liststring ParseCityInput(string input) { if (string.IsNullOrWhiteSpace(input)) return new Liststring(); return input.Split(、, StringSplitOptions.RemoveEmptyEntries) .Select(s s.Trim()) .Where(s !string.IsNullOrWhiteSpace(s)) .ToList(); } /// summary /// /// /summary public void Demo() { // 城市坐标数据 Dictionarystring, 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)}, }; Liststring 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(); Liststring mustCities ParseCityInput(mustInput); Liststring banCities ParseCityInput(banInput); // 统一绑定约束 void SetConstraint(FloydPathPlanner p) { p.MustPassCities new Liststring(mustCities); p.BanCities new HashSetstring(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); } } } }输出