最短路径算法是一个比较常见的用于查找2点之间最短路径的方案。在工作中，由于涉及要查找2点之间的最短路径的场景，所以特此记录一下 算法思想 美国应用数学家Richard Bellman (理查德.贝尔曼, 动态规划的提出者)于1958 年发表了该算法。此外Lester Ford在1956年也发表了该算法。因此这个算法叫做Bellman-Ford算法。 Bellman-Ford算法是一种基于逐次逼近思想进行最短路径求解的算法。其可以被应用在带负权的有向图中，Bellman-ford 算法比dijkstra算法更具普遍性，因为它对边没有要求，可以处理负权边与负权回路。缺点是时间复杂度过高，高达O(VE), V为顶点数，E为边数。 其核心思想为：对于任意一个具有n个节点的图 𝐺 ，任意两点之间的最短路径至多包含 𝑛−1 条边。因此我们可以反复通过对边的松弛来得到当前图的最短路径。 也就是说：第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离；第3轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离…… 松弛操作的含义是更新节点之间的最短距离。 分析 第一步：创建一个带权重 (可以有负权) 的有向图 第二步：选定一个起点（A），将A 到所有节点的 距离都置为 无穷大。 第三步：从节点A开始，将节点最短距离更新，比如 A -> B 直接相连，最短距离是 4 ，A->C 直接相连，距离是 2 。 第四步：最差的情况下，我们需要 V （节点个数）次这样的操作。一个节点最短路径需要被调整 V 次。 第五步：注意右上角的节点 D 是怎么调整的，因为 B -> D (4+2) = 6 , C -> D (2+4) =6 , E->D (6-5)=1 ，所以被更新. 第五步：经过最大循环次数 or 所有的顶点都有其路径长度且不再变后，检查是否有负循环。 Golang 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 type Edge struct { src int dest int weight float64 } type Graph struct { vertices int edges []Edge } func InitGraph(vertices int) *Graph { return &Graph{ vertices: vertices, edges: make([]Edge, 0), } } func (g *Graph) AddEdge(src, dest int, weight float64) { g.

Map 是每门编程语言的最基础的数据结构，这种数据结构的实现就是 key-value之间的映射关系，每个key都有一个唯一的索引值，通过索引值可以很快的找到对应的值。 Map 也是程序中最常见的数据结构，我们的项目中有大量的数据需要加载到内存中，而且需要高频访问，无疑 map 就是最好的选择，但是众所周知，Map是不支持并发访问的。 如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 func main() { var m = make(map[string]int,10) // 初始化一个map go func() { for { m["abc"] = 1 //设置key } }() go func() { for { _ = m["def"] //访问这个map } }() select {} } 虽然这段代码的不同goroutine 是各自在操作不同的元素，但是运行时检测到同时对 map 对象有并发访问，就会直接 panic。 如何实现一个线程安全的 map 类型 最简单的方式必然是加锁访问这里不再赘述了。