最短路径模板

一句话说明

最短路径算法用于求图中两点之间的最短距离。

💻 模板代码

🎯 算法对比

算法	适用场景	时间复杂度	特点
Dijkstra	无负权边	O((V+E)logV)	最常用，不能处理负权
Bellman-Ford	允许负权边	O(V*E)	能检测负环
SPFA	允许负权边	平均O(E)	Bellman-Ford优化版
Floyd	全源最短路	O(V³)	简洁，适合小图

💡 使用场景

• Dijkstra：网络路由、GPS导航
• Bellman-Ford：货币兑换、检测负环
• Floyd：城市间距离、传递闭包
• SPFA：一般图的最短路径

Go 代码

import "container/heap"
 
// Dijkstra算法
func dijkstra(graph map[int][][2]int, start int) map[int]int {
    dist := make(map[int]int)
    for node := range graph {
        dist[node] = math.MaxInt32
    }
    dist[start] = 0
 
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, &Item{node: start, dist: 0})
 
    visited := make(map[int]bool)
 
    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        node := item.node
 
        if visited[node] {
            continue
        }
        visited[node] = true
 
        for _, edge := range graph[node] {
            neighbor, weight := edge[0], edge[1]
            newDist := dist[node] + weight
 
            if newDist < dist[neighbor] {
                dist[neighbor] = newDist
                heap.Push(pq, &Item{node: neighbor, dist: newDist})
            }
        }
    }
 
    return dist
}
 
// 优先队列实现
type Item struct {
    node int
    dist int
}
 
type PriorityQueue []*Item
 
func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
 
func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*Item))
}
 
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

---

返回：算法模板