/* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Floyd-Warshall Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/11 22:36 # User : geovindu # Product : GoLand # Project : goalgorithms # File : floydwarshall.go */ package floydwarshall import ( fmt os sort strings golang.org/x/image/font/opentype gonum.org/v1/plot gonum.org/v1/plot/font gonum.org/v1/plot/plotter gonum.org/v1/plot/plotutil gonum.org/v1/plot/text gonum.org/v1/plot/vg ) const INF 1e18 // City 城市坐标实体 type City struct { Name string X float64 Y float64 } // RoadGraph Floyd全源图距离矩阵前驱矩阵 type RoadGraph struct { cityList []string nameIdx map[string]int n int dist [][]float64 // 距离矩阵 prev [][]int // 前驱矩阵用于回溯路径 } func NewRoadGraph(cityNames []string) *RoadGraph { n : len(cityNames) nameIdx : make(map[string]int, n) for i, name : range cityNames { nameIdx[name] i } // 初始化距离矩阵 dist : make([][]float64, n) prev : make([][]int, n) for i : 0; i n; i { dist[i] make([]float64, n) prev[i] make([]int, n) for j : 0; j n; j { dist[i][j] INF prev[i][j] -1 } dist[i][i] 0 } return RoadGraph{ cityList: cityNames, nameIdx: nameIdx, n: n, dist: dist, prev: prev, } } // AddEdge 添加双向道路 func (g *RoadGraph) AddEdge(from, to string, weight float64) { u : g.nameIdx[from] v : g.nameIdx[to] g.dist[u][v] weight g.dist[v][u] weight g.prev[u][v] u g.prev[v][u] v } // FloydRun 执行Floyd-Warshall 全源最短路更新dist与prev func (g *RoadGraph) FloydRun() { n : g.n for k : 0; k n; k { for i : 0; i n; i { for j : 0; j n; j { if g.dist[i][k]g.dist[k][j] g.dist[i][j] { g.dist[i][j] g.dist[i][k] g.dist[k][j] g.prev[i][j] g.prev[k][j] } } } } } // GetPath 回溯路径同时过滤禁行城市 func (g *RoadGraph) GetPath(start, end string, banSet map[string]bool) (float64, []string) { u, okU : g.nameIdx[start] v, okV : g.nameIdx[end] if !okU || !okV || g.dist[u][v] INF { return INF, nil } // 回溯索引路径 var idxPath []int cur : v for cur ! -1 { idxPath append(idxPath, cur) cur g.prev[u][cur] } sort.Slice(idxPath, func(i, j int) bool { return i j }) // 转城市名称 var path []string for _, idx : range idxPath { city : g.cityList[idx] if banSet[city] { return INF, nil } path append(path, city) } return g.dist[u][v], path } // PathPlanner 规划器约束 绘图 type PathPlanner struct { graph *RoadGraph cityMap map[string]*City MustPass []string BanCities map[string]bool } func NewPathPlanner(g *RoadGraph, cityMap map[string]*City) *PathPlanner { return PathPlanner{ graph: g, cityMap: cityMap, BanCities: make(map[string]bool), } } func (p *PathPlanner) CalcRoute(start, end string) (float64, []string) { total, path : p.graph.GetPath(start, end, p.BanCities) if path nil || len(path) 0 { return INF, nil } // 校验必经城市 for _, req : range p.MustPass { has : false for _, c : range path { if c req { has true break } } if !has { return INF, nil } } return total, path } // DrawMap 生成PNG路网图偏移充足显示负坐标城市 func (p *PathPlanner) DrawMap(savePath string, highlight []string) error { plt : plot.New() plt.Title.Text China City Highway Network | Shortest Path Highlighted plt.X.Label.Text X Coord plt.Y.Label.Text Y Coord cjkFont : loadCJKFont() // 1. 全部灰色路网 var allRoadXY plotter.XYs drawn : make(map[string]bool) for _, frm : range p.graph.cityList { cF : p.cityMap[frm] for _, to : range p.graph.cityList { key1 : frm | to key2 : to | frm if drawn[key1] || drawn[key2] { continue } u : p.graph.nameIdx[frm] v : p.graph.nameIdx[to] if p.graph.dist[u][v] INF { continue } drawn[key1] true cT : p.cityMap[to] allRoadXY append(allRoadXY, plotter.XY{X: cF.X, Y: cF.Y}) allRoadXY append(allRoadXY, plotter.XY{X: cT.X, Y: cT.Y}) } } allRoadLine, err : plotter.NewLine(allRoadXY) if err ! nil { return err } allRoadLine.LineStyle.Color plotutil.Color(11) allRoadLine.LineStyle.Width vg.Length(1) plt.Add(allRoadLine) // 2. 最优路径红色粗线 var pathXY plotter.XYs for _, cityName : range highlight { city : p.cityMap[cityName] pathXY append(pathXY, plotter.XY{X: city.X, Y: city.Y}) } pathLine, err : plotter.NewLine(pathXY) if err ! nil { return err } pathLine.LineStyle.Color plotutil.Color(51) pathLine.LineStyle.Width vg.Length(4) plt.Add(pathLine) // 3. 城市蓝色散点节点 var pointXY plotter.XYs for _, city : range p.cityMap { pointXY append(pointXY, plotter.XY{X: city.X, Y: city.Y}) } scatter, err : plotter.NewScatter(pointXY) if err ! nil { return err } scatter.GlyphStyle.Color plotutil.Color(31) scatter.GlyphStyle.Radius vg.Length(8) plt.Add(scatter) // 4. 城市中文名称标签 var cityLabels plotter.XYLabels var labelStyles []text.Style cjkHandler : text.Plain{ Fonts: font.DefaultCache, } for _, city : range p.cityMap { cityLabels.XYs append(cityLabels.XYs, plotter.XY{X: city.X 0.2, Y: city.Y 0.15}) cityLabels.Labels append(cityLabels.Labels, city.Name) labelStyles append(labelStyles, text.Style{ Font: cjkFont, Handler: cjkHandler, }) } labelPlotter, err : plotter.NewLabels(cityLabels) if err ! nil { return err } labelPlotter.TextStyle labelStyles plt.Add(labelPlotter) // 保存图片 err plt.Save(12*vg.Inch, 9*vg.Inch, savePath) if err ! nil { return err } fmt.Printf(✅ 路网图片已保存%s\n, savePath) return nil } func loadCJKFont() font.Font { fontPaths : []string{ C:\\Windows\\Fonts\\STXIHEI.TTF, C:\\Windows\\Fonts\\AdobeHeitiStd-Regular.otf, C:\\Windows\\Fonts\\msyh.ttc, C:\\Windows\\Fonts\\simsun.ttc, } for _, path : range fontPaths { fontData, err : os.ReadFile(path) if err ! nil { continue } var ttf *opentype.Font if strings.HasSuffix(strings.ToLower(path), .ttc) { col, err : opentype.ParseCollection(fontData) if err ! nil { continue } if col.NumFonts() 0 { ttf, err col.Font(0) if err ! nil { continue } } else { continue } } else { ttf, err opentype.Parse(fontData) if err ! nil { continue } } cjkFace : font.Face{ Font: font.Font{Typeface: CJK}, Face: ttf, } font.DefaultCache.Add(font.Collection{cjkFace}) plot.DefaultTextHandler text.Plain{ Fonts: font.DefaultCache, } return font.Font{Typeface: CJK, Size: vg.Points(8)} } return font.Font{} } // 工具函数 func joinPath(path []string) string { if len(path) 0 { return 无路线 } return strings.Join(path, → ) } func parseCityInput(s string) []string { s strings.TrimSpace(s) if s { return nil } parts : strings.Split(s, 、) var res []string for _, p : range parts { p strings.TrimSpace(p) if p ! { res append(res, p) } } return res } func setConstraint(planner *PathPlanner, must []string, ban []string) { planner.MustPass must planner.BanCities make(map[string]bool) for _, c : range ban { planner.BanCities[c] true } } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看言語成了邀功盡責的功臣還需要行爲每日來值班嗎 # 描述Floyd-Warshall Algorithms # Author : geovindu,Geovin Du 涂聚文. # IDE : goLang 2024.3.6 go 26.2 # os : windows 10 # database : mysql 9.0 sql server 2019, postgreSQL 17.0 Oracle 21c Neo4j # Datetime : 2026/7/11 22:41 # User : geovindu # Product : GoLand # Project : goalgorithms # File : floydwarshallbll.go */ package bll import ( fmt goalgorithms/floydwarshall strings ) func FloydWarshallMain() { // 城市坐标数据 cityData : map[string]*floydwarshall.City{ 深圳: {Name: 深圳, X: 5, Y: 0}, 惠州: {Name: 惠州, X: 6, Y: 1}, 东莞: {Name: 东莞, X: 4, Y: 0}, 广州: {Name: 广州, X: 3, Y: 0}, 佛山: {Name: 佛山, X: 2, Y: 0}, 肇庆: {Name: 肇庆, X: 1, Y: 1}, 梧州: {Name: 梧州, X: -2, Y: 2}, 桂林: {Name: 桂林, X: -3, Y: 4}, 柳州: {Name: 柳州, X: -4, Y: 3}, 南宁: {Name: 南宁, X: -5, Y: 1}, 韶关: {Name: 韶关, X: 2, Y: 4}, 河源: {Name: 河源, X: 7, Y: 3}, 赣州: {Name: 赣州, X: 8, Y: 6}, 吉安: {Name: 吉安, X: 9, Y: 9}, 南昌: {Name: 南昌, X: 10, Y: 8}, 萍乡: {Name: 萍乡, X: 7, Y: 8}, 长沙: {Name: 长沙, X: 6, Y: 9}, 株洲: {Name: 株洲, X: 6, Y: 8}, 衡阳: {Name: 衡阳, X: 6, Y: 6}, 郴州: {Name: 郴州, X: 6, Y: 4}, 九江: {Name: 九江, X: 11, Y: 9}, 武汉: {Name: 武汉, X: 9, Y: 11}, 郑州: {Name: 郑州, X: 10, Y: 14}, 西安: {Name: 西安, X: 7, Y: 15}, 福州: {Name: 福州, X: 13, Y: 7}, 厦门: {Name: 厦门, X: 14, Y: 4}, } // 提取城市名称列表 var cityList []string for k : range cityData { cityList append(cityList, k) } // 1. 里程路网 KM graphKm : floydwarshall.NewRoadGraph(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.FloydRun() // 2. 耗时路网 Hour graphHour : floydwarshall.NewRoadGraph(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.FloydRun() // 3. 路费路网 Cost graphCost : floydwarshall.NewRoadGraph(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.FloydRun() // 初始化规划器 planKm : floydwarshall.NewPathPlanner(graphKm, cityData) planHour : floydwarshall.NewPathPlanner(graphHour, cityData) planCost : floydwarshall.NewPathPlanner(graphCost, cityData) // 打印城市列表 fmt.Println( Go Floyd-Warshall 全源高速路径规划系统 ) fmt.Printf(可用城市%s\n, strings.Join(cityList, 、)) fmt.Println(----------------------------------------) // 控制台输入 var start, end, mustInput, banInput string fmt.Print(输入起点城市) fmt.Scanln(start) fmt.Print(输入终点城市) fmt.Scanln(end) fmt.Print(必须途经城市多城顿号分隔无直接回车) fmt.Scanln(mustInput) fmt.Print(禁止绕行城市多城顿号分隔无直接回车) fmt.Scanln(banInput) mustList : parseCityInput(mustInput) banList : parseCityInput(banInput) // 绑定约束 setConstraint(planKm, mustList, banList) setConstraint(planHour, mustList, banList) setConstraint(planCost, mustList, banList) // 计算路线 kmTotal, kmPath : planKm.CalcRoute(start, end) hourTotal, hourPath : planHour.CalcRoute(start, end) costTotal, costPath : planCost.CalcRoute(start, end) // 输出结果 fmt.Println(\n) fmt.Printf(【%s → %s 规划结果】\n, start, end) fmt.Println() if len(kmPath) 0 { fmt.Printf( 最短里程%.0f km | 路线%s\n, kmTotal, dujoinPath(kmPath)) } else { fmt.Println( 最短里程无可行路线约束过滤) } if len(hourPath) 0 { fmt.Printf(⏰ 最短耗时%.1f h | 路线%s\n, hourTotal, dujoinPath(hourPath)) } else { fmt.Println(⏰ 最短耗时无可行路线约束过滤) } if len(costPath) 0 { fmt.Printf( 最低路费%.0f 元 | 路线%s\n, costTotal, dujoinPath(costPath)) } else { fmt.Println( 最低路费无可行路线约束过滤) } fmt.Println() // 生成PNG图片 if len(kmPath) 0 { err : planKm.DrawMap(floyd_route_map.png, kmPath) if err ! nil { fmt.Printf(绘图失败%v\n, err) } } } // 工具函数 func dujoinPath(path []string) string { if len(path) 0 { return 无路线 } return strings.Join(path, → ) } func parseCityInput(s string) []string { s strings.TrimSpace(s) if s { return nil } parts : strings.Split(s, 、) var res []string for _, p : range parts { p strings.TrimSpace(p) if p ! { res append(res, p) } } return res } func setConstraint(planner *floydwarshall.PathPlanner, must []string, ban []string) { planner.MustPass must planner.BanCities make(map[string]bool) for _, c : range ban { planner.BanCities[c] true } }输出