终于搞懂Dijkstra算法了

文章目录

• 示例1
• 示例2
• 参考资料

Dijkstra算法用来解决单源最短路径问题，思路如下

将图中顶点分为2部分
S：已经找到最短路径的顶点
U：剩下的顶点
假设初始顶点为v0， 那么S：{v0}， U：{剩下的顶点}
从U中找到一个距离v0最近的一个顶点，假设为x，将x从U中移动到S。
对于U中的任意顶点y，如果d[v0][x] + d[x][y] < d[v0][y]， 则d[v0][y] = d[v0][x] + d[x][y]。
如此循环，直到处理完U中所有顶点。

Dijkstra是按照路径长度递增的顺序，来求解v0到其他顶点的所有最短路径。
是一个贪心算法。

示例1

代码

// g[i][j]：顶点i、顶点j之间的距离
// 如果i、j直连，就是边ij的长度，
// 否则对应math.MaxInt32【i == j 时，也是math.MaxInt32】

// 返回 顶点 start 到 其他顶点 的最短距离
func shortestPath(g [][]int, start int) []int {
	// 顶点个数
	n := len(g)
	// 存储 顶点 start 到 其他顶点 的最短距离
	distance := make([]int, n)
	// start -> start的距离为0
	distance[start] = 0
	// 标记顶点的访问状态
	visited := make([]bool, n)
	// 顶点 start 加入到 S
	visited[start] = true
	// 确定剩下 n-1 个 顶点 的最短距离
	for i := 1; i < n; i++ {
		// 在 U 中找到最短路径对应的顶点
		// 需要比边的最大值要大
		min := math.MaxInt32 + 1
		var k int
		for j := 0; j < n; j++ {
			if !visited[j] && g[start][j] < min {
				min = g[start][j]
				k = j
			}
		}
		// 顶点 k 加入到 S
		visited[k] = true
		distance[k] = min
		// 更新 U 中的路径
		for j := 0; j < n; j++ {
			if !visited[j] && min+g[k][j] < g[start][j] {
				g[start][j] = min + g[k][j]
			}
		}
	}
	return distance
}

1个示例

输入

func Test_xx(t *testing.T) {
	g := [][]int{
		{math.MaxInt32, 4, math.MaxInt32, 2, math.MaxInt32},
		{4, math.MaxInt32, 4, 1, math.MaxInt32},
		{math.MaxInt32, 4, math.MaxInt32, 1, 3},
		{2, 1, 1, math.MaxInt32, 7},
		{math.MaxInt32, math.MaxInt32, 3, 7, math.MaxInt32},
	}
	fmt.Println(shortestPath(g, 0))
}

输出

[0 3 3 2 6]

再给一个示例

输入

func Test_xx(t *testing.T) {
	g := [][]int{
		{math.MaxInt32, math.MaxInt32, 10, math.MaxInt32, 30, 100},
		{math.MaxInt32, math.MaxInt32, 5, math.MaxInt32, math.MaxInt32, math.MaxInt32},
		{math.MaxInt32, math.MaxInt32, math.MaxInt32, 50, math.MaxInt32, math.MaxInt32},
		{math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32, 10},
		{math.MaxInt32, math.MaxInt32, math.MaxInt32, 20, math.MaxInt32, 60},
		{math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32, math.MaxInt32},
	}
	fmt.Println(shortestPath(g, 0))
}

输出

[0 2147483647 10 50 30 60]

上述代码会修改输入g，下面给一个不修改g的版本

示例2

func shortestPath2(g [][]int, start int) []int {
	n := len(g)
	distance := make([]int, n)
	for i := 0; i < n; i++ {
		distance[i] = g[start][i]
	}
	distance[start] = 0
	visited := make([]bool, n)
	visited[start] = true
	for i := 1; i < n; i++ {
		min := math.MaxInt32 + 1
		var k int
		for j := 0; j < n; j++ {
			if !visited[j] && distance[j] < min {
				min = distance[j]
				k = j
			}
		}
		visited[k] = true
		for j := 0; j < n; j++ {
			if !visited[j] && min+g[k][j] < distance[j] {
				distance[j] = min + g[k][j]
			}
		}
	}
	return distance
}

参考资料

https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-dijkstra