Go语言实现图的最短路径计数（详解图算法中的最短路径数量统计）

算法思路

我们采用以下策略：

1. 使用 BFS 遍历图，因为 BFS 天然按层（距离）扩展，能保证第一次访问某节点时就是最短距离。
2. 维护两个数组：dist[] 记录从起点到各点的最短距离，count[] 记录到达该点的最短路径数量。
3. 当发现一条新路径长度等于当前最短距离时，累加路径数量；若更短，则更新距离并重置计数。

Go语言代码实现

下面是一个完整的 Go 程序，用于计算无权无向图中从起点到终点的最短路径数量：

package mainimport (	"fmt")// Graph 表示邻接表形式的图type Graph struct {	adj map[int][]int}// NewGraph 创建新图func NewGraph() *Graph {	return &Graph{		adj: make(map[int][]int),	}}// AddEdge 添加无向边func (g *Graph) AddEdge(u, v int) {	g.adj[u] = append(g.adj[u], v)	g.adj[v] = append(g.adj[v], u)}// CountShortestPaths 计算从 start 到 end 的最短路径数量func (g *Graph) CountShortestPaths(start, end int) int {	if start == end {		return 1	}	// 初始化距离和计数	dist := make(map[int]int)	count := make(map[int]int)	for node := range g.adj {		dist[node] = -1 // -1 表示未访问	}	dist[start] = 0	count[start] = 1	// BFS 队列	queue := []int{start}	for len(queue) > 0 {		u := queue[0]		queue = queue[1:]		for _, v := range g.adj[u] {			if dist[v] == -1 {				// 第一次访问 v				dist[v] = dist[u] + 1				count[v] = count[u]				queue = append(queue, v)			} else if dist[v] == dist[u]+1 {				// 找到另一条相同长度的最短路径				count[v] += count[u]			}		}	}	return count[end]}func main() {	g := NewGraph()	// 构建示例图	g.AddEdge(0, 1)	g.AddEdge(0, 2)	g.AddEdge(1, 3)	g.AddEdge(2, 3)	g.AddEdge(3, 4)	start, end := 0, 4	result := g.CountShortestPaths(start, end)	fmt.Printf("从 %d 到 %d 的最短路径数量: %d\n", start, end, result)}

代码解析

• Graph 结构体使用 map 实现邻接表，灵活支持任意节点编号。
• BFS 队列确保按距离递增顺序处理节点。
• 当遇到未访问节点（dist[v] == -1），记录距离并继承路径数。
• 若已访问但距离相等（dist[v] == dist[u] + 1），说明找到新最短路径，累加计数。

运行结果

以上示例图结构如下：

0 —— 1 —— 3 —— 4|         /|       /2 ————

从 0 到 4 有两条最短路径（长度为 3）：

1. 0 → 1 → 3 → 4
2. 0 → 2 → 3 → 4

程序输出：

从 0 到 4 的最短路径数量: 2

应用场景与扩展

这种 Go语言最短路径计数 方法适用于：

• 社交网络中两人之间的最短关系链数量
• 路由协议中备选最优路径数
• 游戏地图中角色移动的最优策略多样性

如果你需要处理带权图，可改用 Dijkstra 算法配合类似计数逻辑，但需注意权重非负。

总结

通过本教程，你学会了如何用 Go语言实现图的最短路径计数。核心在于结合 BFS 与动态更新路径数量。掌握这一技巧，不仅能解决面试题，还能应用于实际工程问题。

希望这篇关于 图算法Go实现 和 最短路径数量统计 的教程对你有帮助！动手试试修改图结构，观察路径数量变化吧。