最短路径问题-Dijkstra算法

写在前面

前几天做leetcode发现有个题目需要用到最短路径问题，于是专门学习了一下Dijkstra算法

上次接触Dijkstra算法还是在大学期间，已经忘记的差不多了。今天在网上搜了一下算法，思想并不难。看懂之后自己实现了一下，经过短暂的调试，可以成功运行

算法思想

Dijkstra算法其实是一种贪心算法。

什么是贪心算法？

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

举个例子：

• 打个比方，吃自助餐，目标是吃回本，那么胃有限那么每次都仅最贵的吃。
• 上学时，麻麻说只能带5个苹果，你想带最多，那么选五个苹果你每次都选最大的那个五次下来你就选的最重的那个。

算法核心：

对于第二步，dist|s,v|=min(dist|s,v|, dist|s,j|+dist|j,v|)

对第二步不太容易理解，下面通过代码来分析

代码

/*
迪杰斯特拉算法:解决一个点到其他所有点的最短路径问题
*/

const (
	Max = 1 << 10
)

// 已知点的集合points和各个点之间的有向边长度edges，求从start点开始到剩余所有点的最短路径分别是多少
func Dijkstra(points []int, edges [][]int, start int) map[int]int {
	// 原始点集v
	v := make(map[int]struct{})
	for i := range points {
		v[points[i]] = struct{}{}
	}

	// 已经加入s的集合
	s := make(map[int]struct{})

	// 将第一个点point[start]从v集合移出，并加入s集合
	delete(v, start)
	s[start] = struct{}{}

	// 记录开始节点到其他各个节点最短距离
	paths := make(map[int]int)

	// 初始化paths
	for i := range edges[start] {
		paths[i] = edges[start][i]
	}

	for len(v) > 0 {
		// 只要v不为空，则一直循环
		// 1.找出paths中最小路径的点
		minPoint := 0
		for point, path := range paths {
			if _, ok := s[point]; ok {
				continue
			}
			if minPoint == 0 {
				minPoint = point
				continue
			}
			if path < paths[minPoint] {
				minPoint = point
			}
		}

		// 2.将minPoint点加入s集合
		s[minPoint] = struct{}{}

		// 3.将minPoint点从v集合中移除
		delete(v, minPoint)

		// 4.更新paths:如果start讲过点point到v中每个节点的距离更近则更是paths
		for point, _ := range v {
			newPath := paths[minPoint] + edges[minPoint][point]
			if newPath < paths[point] {
				paths[point] = newPath
			}
		}
	}

	return paths
}

测试

func main() {
	points := []int{1, 2, 3, 4, 5, 6}
	edges := [][]int{
		{},
		{Max, Max, 10, Max, Max, Max, 3},
		{Max, Max, Max, 7, 5, Max, Max},
		{Max, Max, Max, Max, Max, Max, Max},
		{Max, 3, Max, Max, Max, 7, Max},
		{Max, Max, Max, Max, Max, Max, Max},
		{Max, Max, 2, Max, 6, 1, Max},
	}
	start := 1
	result := Dijkstra(points, edges, start)
	for i := range points {
		if points[i] == start {
			continue
		}
		fmt.Printf("节点:%d 到节点:%d 的最短距离是:%d\n", start, points[i], result[points[i]])
	}
}

结果

节点:1 到节点:2 的最短距离是:5
节点:1 到节点:3 的最短距离是:12
节点:1 到节点:4 的最短距离是:9
节点:1 到节点:5 的最短距离是:4
节点:1 到节点:6 的最短距离是:3

源代码：https://github.com/ZBIGBEAR/algorithm/blob/master/dijkstra/dijkstra.go

总结

本文可能对算法讲解的不是很清楚，可以阅读参考文章1和2，这两篇文章讲解的挺详细的，图文并茂。本文更多的是实现了次算法并做个记录。

参考

[1][最短路径问题]—Dijkstra 算法最详解

[2]Dijkstra算法详细(单源最短路径算法) 

[3]https://github.com/ZBIGBEAR/algorithm/blob/master/dijkstra/dijkstra.go