适用于存在负权边,题目要求最短路不超过k条边,还可以检测是否存在回路
核心思想是 松弛操作(枚举所有边)
首先n次迭代,每一次循环所有边。我们这里用a,b,w表示存在一条从a走到b的边,权重是w。这里存边方式有很多种,可以用邻接表,结构体等。遍历所有边的时候更新一下其他点的距离,和Dijkstra算法类似,用当前这个点更新和它相连的点距离起点的距离。我们这里用dist数组表示每个点到起点的距离,那么更新操作就是dist[b]=min(dist[b],dist[a]+w),这样就可以更新和a相连的b点距离起点的距离,这个更新的过程就是”松弛操作”。忘了说的一点就是在循环所有边的时候,每一次循环要先把dist数组备份一下,防止串联,循环n次之后对所有的边一定满足dist[b]<=dist[a]+w,这个叫”三角不等式“
但是注意如果图中有负权回路的话,最短路就不一定存在了
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
标签:dist,所有,更新,ford,算法,循环,距离,Bellman From: https://www.cnblogs.com/-Rebecca/p/16890186.html