go: Dijkstra Algorithms

/* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 # 描述： # 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/8 23:07 # User : geovindu # Product : GoLand # Project : goalgorithms # File : dijkstraalgorithms.go */ package main import ( "bufio" "container/heap" "fmt" "math" "os" //"sort" //"strconv" "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" ) var inputScanner = bufio.NewScanner(os.Stdin) // ====================== 1. 分层结构体封装 ====================== // City 城市坐标定义 type City struct { Name string X float64 Y float64 } // RoadGraph 路网邻接表，统一权重 type RoadGraph struct { adj map[string]map[string]float64 // 邻接表：起点->{终点:权重} } // PathPlanner 路径规划器，承载约束条件 type PathPlanner struct { graph *RoadGraph mustPass []string // 必须途经城市 banCitySet map[string]bool // 禁止绕行城市集合 cityCoordMap map[string]City // 城市坐标映射 } // NewRoadGraph 新建空路网 func NewRoadGraph() *RoadGraph { return &RoadGraph{ adj: make(map[string]map[string]float64), } } // AddEdge 添加双向高速路段 func (g *RoadGraph) AddEdge(from, to string, weight float64) { if _, ok := g.adj[from]; !ok { g.adj[from] = make(map[string]float64) } g.adj[from][to] = weight if _, ok := g.adj[to]; !ok { g.adj[to] = make(map[string]float64) } g.adj[to][from] = weight } // NewPlanner 初始化规划器 func NewPlanner(g *RoadGraph, cityCoords map[string]City) *PathPlanner { return &PathPlanner{ graph: g, mustPass: make([]string, 0), banCitySet: make(map[string]bool), cityCoordMap: cityCoords, } } // SetMustPass 设置必经途经点 func (p *PathPlanner) SetMustPass(cities []string) { p.mustPass = cities } // AddBanCity 添加禁止绕行城市 func (p *PathPlanner) AddBanCity(city string) { p.banCitySet[city] = true } // ClearBanCity 清空禁止城市 func (p *PathPlanner) ClearBanCity() { p.banCitySet = make(map[string]bool) } // ====================== 2. Dijkstra 最小堆实现 ====================== type Item struct { city string distance float64 index int path []string // 当前已走路径，用于约束校验 } type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].distance < pq[j].distance } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] old[n-1] = nil item.index = -1 *pq = old[0 : n-1] return item } // contains 判断切片包含城市 func contains(list []string, target string) bool { for _, v := range list { if v == target { return true } } return false } // allPassCheck 校验路径是否经过所有必经点 func allPassCheck(path []string, must []string) bool { for _, req := range must { if !contains(path, req) { return false } } return true } // DijkstraWithConstraint 带约束：禁行城市 + 必经途经点 func (p *PathPlanner) DijkstraWithConstraint(start, end string) (float64, []string) { inf := math.Inf(1) dist := make(map[string]float64) prev := make(map[string]string) for city := range p.graph.adj { dist[city] = inf } dist[start] = 0 pq := make(PriorityQueue, 0) heap.Init(&pq) heap.Push(&pq, &Item{ city: start, distance: 0, path: []string{start}, }) visited := make(map[string]bool) bestTotal := inf var bestPath []string for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) currCity := item.city currDist := item.distance currPath := item.path // 过滤禁止通行城市 if p.banCitySet[currCity] { continue } if visited[currCity] { continue } // 到达终点，校验是否满足全部必经点 if currCity == end { if allPassCheck(currPath, p.mustPass) { if currDist < bestTotal { bestTotal = currDist bestPath = make([]string, len(currPath)) copy(bestPath, currPath) } } continue } visited[currCity] = true // 遍历邻接节点 for neighbor, weight := range p.graph.adj[currCity] { if p.banCitySet[neighbor] || visited[neighbor] { continue } newDist := currDist + weight if newDist < dist[neighbor] { dist[neighbor] = newDist prev[neighbor] = currCity newPath := make([]string, len(currPath)+1) copy(newPath, currPath) newPath[len(currPath)] = neighbor heap.Push(&pq, &Item{ city: neighbor, distance: newDist, path: newPath, }) } } } return bestTotal, bestPath } func (p *PathPlanner) DrawRoutePNG(outPath string, route []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" loadCJKFont() // 1. 全部灰色路网 var allRoadXY plotter.XYs for from, neighbors := range p.graph.adj { fCity := p.cityCoordMap[from] for to := range neighbors { tCity := p.cityCoordMap[to] allRoadXY = append(allRoadXY, plotter.XY{X: fCity.X, Y: fCity.Y}) allRoadXY = append(allRoadXY, plotter.XY{X: tCity.X, Y: tCity.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 route { city := p.cityCoordMap[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.cityCoordMap { 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 for _, city := range p.cityCoordMap { cityLabels.XYs = append(cityLabels.XYs, plotter.XY{X: city.X + 0.2, Y: city.Y + 0.15}) cityLabels.Labels = append(cityLabels.Labels, city.Name) } labelPlotter, err := plotter.NewLabels(cityLabels) if err != nil { return err } plt.Add(labelPlotter) // 保存图片 err = plt.Save(12*vg.Inch, 9*vg.Inch, outPath) if err != nil { return err } fmt.Printf("路网图已保存至: %s\n", outPath) return nil } // ====================== 工具函数 ====================== func joinPath(path []string) string { var sb strings.Builder for i, s := range path { if i > 0 { sb.WriteString(" → ") } sb.WriteString(s) } return sb.String() } func inputString(prompt string) string { fmt.Print(prompt) inputScanner.Scan() return strings.TrimSpace(inputScanner.Text()) } func splitCityInput(input string) []string { if input == "" { return nil } parts := strings.Split(input, "、") var res []string for _, p := range parts { p = strings.TrimSpace(p) if p != "" { res = append(res, p) } } return res } func loadCJKFont() { fontPaths := []string{ "C:\\Windows\\Fonts\\msyh.ttc", "C:\\Windows\\Fonts\\simhei.ttf", "C:\\Windows\\Fonts\\simsun.ttc", } for _, path := range fontPaths { fontData, err := os.ReadFile(path) if err != nil { continue } 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 } } /* # 版权所有 2026 ©涂聚文有限公司™ ® # 许可信息查看：言語成了邀功盡責的功臣，還需要行爲每日來值班嗎 # 描述： # 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/8 23:07 # User : geovindu # Product : GoLand # Project : goalgorithms # File : main.go */ package main import ( "fmt" "sort" "strings" ) //TIP <p>To run your code, right-click the code and select <b>Run</b>.</p> <p>Alternatively, click // the <icon src="AllIcons.Actions.Execute"/> icon in the gutter and select the <b>Run</b> menu item from here.</p> func main() { // 1. 城市坐标数据 cityCoords := map[string]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}, } // 2. 构建里程路网 gKM := NewRoadGraph() gKM.AddEdge("深圳", "惠州", 75) gKM.AddEdge("深圳", "广州", 140) gKM.AddEdge("深圳", "东莞", 65) gKM.AddEdge("惠州", "河源", 90) gKM.AddEdge("东莞", "广州", 50) gKM.AddEdge("广州", "韶关", 190) gKM.AddEdge("广州", "佛山", 25) gKM.AddEdge("佛山", "肇庆", 70) gKM.AddEdge("肇庆", "梧州", 210) gKM.AddEdge("梧州", "桂林", 260) gKM.AddEdge("桂林", "柳州", 170) gKM.AddEdge("柳州", "南宁", 220) gKM.AddEdge("韶关", "赣州", 230) gKM.AddEdge("河源", "赣州", 180) gKM.AddEdge("赣州", "吉安", 240) gKM.AddEdge("赣州", "南昌", 390) gKM.AddEdge("吉安", "南昌", 215) gKM.AddEdge("吉安", "萍乡", 280) gKM.AddEdge("萍乡", "长沙", 150) gKM.AddEdge("长沙", "武汉", 280) gKM.AddEdge("长沙", "株洲", 60) gKM.AddEdge("株洲", "衡阳", 130) gKM.AddEdge("衡阳", "郴州", 180) gKM.AddEdge("郴州", "韶关", 150) gKM.AddEdge("南昌", "九江", 130) gKM.AddEdge("九江", "武汉", 200) gKM.AddEdge("武汉", "郑州", 470) gKM.AddEdge("郑州", "西安", 450) gKM.AddEdge("南昌", "福州", 380) gKM.AddEdge("福州", "厦门", 230) // 耗时路网 gHour := NewRoadGraph() gHour.AddEdge("深圳", "惠州", 1.0) gHour.AddEdge("深圳", "广州", 1.8) gHour.AddEdge("深圳", "东莞", 0.8) gHour.AddEdge("惠州", "河源", 1.3) gHour.AddEdge("东莞", "广州", 0.7) gHour.AddEdge("广州", "韶关", 2.2) gHour.AddEdge("广州", "佛山", 0.4) gHour.AddEdge("佛山", "肇庆", 0.9) gHour.AddEdge("肇庆", "梧州", 2.5) gHour.AddEdge("梧州", "桂林", 3.0) gHour.AddEdge("桂林", "柳州", 2.0) gHour.AddEdge("柳州", "南宁", 2.5) gHour.AddEdge("韶关", "赣州", 2.7) gHour.AddEdge("河源", "赣州", 2.0) gHour.AddEdge("赣州", "吉安", 2.6) gHour.AddEdge("赣州", "南昌", 4.2) gHour.AddEdge("吉安", "南昌", 2.3) gHour.AddEdge("吉安", "萍乡", 3.0) gHour.AddEdge("萍乡", "长沙", 1.6) gHour.AddEdge("长沙", "武汉", 3.0) gHour.AddEdge("长沙", "株洲", 0.8) gHour.AddEdge("株洲", "衡阳", 1.4) gHour.AddEdge("衡阳", "郴州", 2.0) gHour.AddEdge("郴州", "韶关", 1.7) gHour.AddEdge("南昌", "九江", 1.4) gHour.AddEdge("九江", "武汉", 2.1) gHour.AddEdge("武汉", "郑州", 4.8) gHour.AddEdge("郑州", "西安", 4.3) gHour.AddEdge("南昌", "福州", 4.0) gHour.AddEdge("福州", "厦门", 2.4) // 路费路网 gCost := NewRoadGraph() gCost.AddEdge("深圳", "惠州", 35) gCost.AddEdge("深圳", "广州", 65) gCost.AddEdge("深圳", "东莞", 30) gCost.AddEdge("惠州", "河源", 42) gCost.AddEdge("东莞", "广州", 25) gCost.AddEdge("广州", "韶关", 85) gCost.AddEdge("广州", "佛山", 15) gCost.AddEdge("佛山", "肇庆", 35) gCost.AddEdge("肇庆", "梧州", 100) gCost.AddEdge("梧州", "桂林", 120) gCost.AddEdge("桂林", "柳州", 70) gCost.AddEdge("柳州", "南宁", 95) gCost.AddEdge("韶关", "赣州", 105) gCost.AddEdge("河源", "赣州", 80) gCost.AddEdge("赣州", "吉安", 110) gCost.AddEdge("赣州", "南昌", 180) gCost.AddEdge("吉安", "南昌", 95) gCost.AddEdge("吉安", "萍乡", 125) gCost.AddEdge("萍乡", "长沙", 65) gCost.AddEdge("长沙", "武汉", 130) gCost.AddEdge("长沙", "株洲", 25) gCost.AddEdge("株洲", "衡阳", 55) gCost.AddEdge("衡阳", "郴州", 80) gCost.AddEdge("郴州", "韶关", 65) gCost.AddEdge("南昌", "九江", 55) gCost.AddEdge("九江", "武汉", 85) gCost.AddEdge("武汉", "郑州", 210) gCost.AddEdge("郑州", "西安", 190) gCost.AddEdge("南昌", "福州", 170) gCost.AddEdge("福州", "厦门", 105) // 初始化三类规划器 planKM := NewPlanner(gKM, cityCoords) planHour := NewPlanner(gHour, cityCoords) planCost := NewPlanner(gCost, cityCoords) // 打印全部城市 var allCities []string for k := range cityCoords { allCities = append(allCities, k) } sort.Strings(allCities) fmt.Println("===== Go 城市高速路径规划系统（带约束+绘图）=====") fmt.Println("可用城市：", strings.Join(allCities, "、")) fmt.Println("------------------------------------------------") // 交互输入 start := inputString("输入起点城市：") end := inputString("输入终点城市：") mustStr := inputString("输入必须途经城市（多城用顿号分隔，无则直接回车）：") banStr := inputString("输入禁止绕行城市（多城用顿号分隔，无则直接回车）：") mustList := splitCityInput(mustStr) banList := splitCityInput(banStr) // 统一设置约束 setConstraint := func(p *PathPlanner) { p.SetMustPass(mustList) p.ClearBanCity() for _, b := range banList { p.AddBanCity(b) } } setConstraint(planKM) setConstraint(planHour) setConstraint(planCost) // 计算三种方案 totalKM, pathKM := planKM.DijkstraWithConstraint(start, end) totalHour, pathHour := planHour.DijkstraWithConstraint(start, end) totalCost, pathCost := planCost.DijkstraWithConstraint(start, end) // 输出结果 fmt.Println("\n====================================================") fmt.Printf("【%s → %s 规划结果】\n", start, end) fmt.Println("====================================================") if len(pathKM) > 0 { fmt.Printf("📏 最短里程：%.0f km | 路线：%s\n", totalKM, joinPath(pathKM)) } else { fmt.Println("📏 最短里程：无可行路线（约束过滤）") } if len(pathHour) > 0 { fmt.Printf("⏰ 最短耗时：%.1f h | 路线：%s\n", totalHour, joinPath(pathHour)) } else { fmt.Println("⏰ 最短耗时：无可行路线（约束过滤）") } if len(pathCost) > 0 { fmt.Printf("💰 最低路费：%.0f 元 | 路线：%s\n", totalCost, joinPath(pathCost)) } else { fmt.Println("💰 最低路费：无可行路线（约束过滤）") } fmt.Println("====================================================") // 绘制路网图（基于里程最优路线） if len(pathKM) > 0 { err := planKM.DrawRoutePNG("route_map.png", pathKM) if err != nil { fmt.Printf("绘图失败：%v\n", err) } } }