Golang 实现 Dijkstra 单源最短路径算法详解

package main

import (
	"fmt"
	"math"
)

// Dijkstra 算法用于计算无向图的最短路径
// graph: 邻接矩阵，-1 表示无连接
// startNode: 起始节点索引
func dijkstra(graph [][]int, startNode int) []int {
	nodesCount := len(graph)
	visited := make([]bool, nodesCount)
	distance := make([]int, nodesCount)

	// 1. 初始化 distance 为最大值，visited 为 false
	for i := 0; i < nodesCount; i++ {
		visited[i] = false
		distance[i] = math.MaxInt32
	}

	// 2. 起点到自身的距离为 0
	distance[startNode] = 0

	// 3. 遍历 nodesCount-1 次，每次找出一个最近节点并更新邻居
	for i := 0; i < nodesCount-1; i++ {
		minDistance := math.MaxInt32
		currentNode := -1

		// 查找距离最小的未访问节点
		for j := 0; j < nodesCount; j++ {
			if !visited[j] && distance[j] < minDistance {
				minDistance = distance[j]
				currentNode = j
			}
		}

		// 如果没有找到可达的未访问节点，提前退出
		if currentNode == -1 {
			break
		}

		// 标记当前节点已访问
		visited[currentNode] = true

		// 更新相邻节点的距离
		for j := 0; j < nodesCount; j++ {
			// 存在边且未被访问时进行松弛
			if graph[currentNode][j] != -1 {
				newDistance := distance[currentNode] + graph[currentNode][j]
				if newDistance < distance[j] {
					distance[j] = newDistance
				}
			}
		}
	}

	return distance
}

func main() {
	// 测试用例：5个节点的无向图
	graph := [][]int{
		{-1, 2, -1, 6, -1},
		{2, -1, 3, 8, 5},
		{-1, 3, -1, -1, 7},
		{6, 8, -1, -1, 9},
		{-1, 5, 7, 9, -1},
	}

	startNode := 0 // 从节点 0 出发
	distances := dijkstra(graph, startNode)

	fmt.Println("Shortest distances from node", startNode, "to all other nodes:")
	for i, d := range distances {
		fmt.Printf("Node %d: %d\n", i, d)
	}
}