Go语言实现Dijkstra最短路径算法（小白也能看懂的图论入门教程）

Go语言实现步骤

我们将使用以下数据结构：

• 邻接表（map[int]map[int]int）表示图
• dist数组记录从起点到各点的最短距离
• visited集合记录已处理的节点
• 优先队列（这里用切片模拟）选择最小距离节点

完整代码实现

// dijkstra.gopackage mainimport (	"fmt"	"math")// Graph 表示图的邻接表type Graph map[int]map[int]int// Dijkstra 实现Dijkstra最短路径算法func Dijkstra(g Graph, start int) map[int]int {	// 初始化距离字典	dist := make(map[int]int)	visited := make(map[int]bool)	// 所有节点初始距离设为无穷大	for node := range g {		dist[node] = math.MaxInt32	}	dist[start] = 0 // 起点距离为0	// 循环直到所有节点都被访问	for len(visited) < len(g) {		// 找到未访问节点中距离最小的		minNode := -1		minDist := math.MaxInt32		for node, d := range dist {			if !visited[node] && d < minDist {				minDist = d				minNode = node			}		}		// 如果找不到有效节点，跳出		if minNode == -1 {			break		}		visited[minNode] = true		// 更新邻居节点的距离		for neighbor, weight := range g[minNode] {			newDist := dist[minNode] + weight			if newDist < dist[neighbor] {				dist[neighbor] = newDist			}		}	}	return dist}func main() {	// 构建一个示例图	graph := Graph{		0: {1: 4, 2: 1},		1: {3: 1},		2: {1: 2, 3: 5},		3: {},	}	startNode := 0	distances := Dijkstra(graph, startNode)	fmt.Printf("从节点 %d 出发的最短路径距离:\n", startNode)	for node, dist := range distances {		if dist == math.MaxInt32 {			fmt.Printf("节点 %d: 不可达\n", node)		} else {			fmt.Printf("节点 %d: %d\n", node, dist)		}	}}

代码详解

1. Graph类型：我们用嵌套map表示图，外层key是节点，内层key是邻居节点，value是边的权重。

2. 初始化：将所有节点距离设为无穷大（math.MaxInt32），起点设为0。

3. 主循环：每次从未访问节点中选出距离最小的节点，标记为已访问。

4. 松弛操作：用当前节点更新其所有邻居的距离，如果通过当前节点到达邻居更短，则更新。

运行结果

运行上述代码，输出如下：

从节点 0 出发的最短路径距离:节点 0: 0节点 1: 3节点 2: 1节点 3: 4

注意事项

- Dijkstra算法不能处理负权边，因为贪心策略在负权情况下会失效。

- 上述实现的时间复杂度为 O(V²)，其中V是节点数。若使用优先队列（如堆），可优化至 O((V+E) log V)。

总结

通过本教程，你已经掌握了如何用Go语言实现Dijkstra算法来求解最短路径问题。这是图论算法中的基础内容，广泛应用于导航系统、网络路由等领域。建议你动手修改图结构，观察不同输入下的输出，加深理解！

掌握Go语言和图论算法，让你的编程能力更上一层楼！