go: Floyd-Warshall Algorithms

/* # 版权所有 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 } }

输出：