bellman-ford算法与差分约束系统[青松学堂]

Bellman-Ford算法算法与差分约束系统与差分约束系统1学堂A单源最短路径问题单源最短路径问题l单源最短路径=Single Source Shortest Path，即在有向图（或无向图）中求解给定点到其他点之间的最短距离l我们已知的方法是lDijkstra算法l暑期集训的时候已经对该算法做过介绍，这里不再重复2学堂ADijkstra算法的局限性算法的局限性l如果边权为负值，Dijkstra算法还正确吗？l求解右图A 至其他点的最短距离l算法步骤：1）标记点A2）DistC=2最小，标记点C3）DistB=3最小，标记点B结束l但是ShortestDistC=1ABC23-23学堂ADijkstra算法的局限性算法的局限性l下图中，A至F的最短路径长度是多少？ABCDEF11-1-1-1-1-4学堂ADijkstra算法的局限性算法的局限性l如果利用Dijkstra算法求解，结果为l标记点A，DistB=-1，标记点BlDistC=0，标记点ClDistD=-1，标记点DlDistE=-2，标记点ElDistF=-1，标记点Fl所求得的距离并不是最短的ABCDEF11-1-1-1-15学堂A错误结果的原因错误结果的原因lDijkstra的缺陷就在于它不能处理负权回路：Dijkstra对于标记过的点就不再进行更新了，所以即使有负权导致最短距离的改变也不会重新计算已经计算过的结果l我们需要新的算法Bellman-Ford6学堂ABellman-Ford算法思想算法思想lBellman-Ford算法基于动态规划，反复用已有的边来更新最短距离lBellman-Ford算法的核心思想松弛lDistu和Distv应当满足一个关系，即Distvdu+wu,v则dv=du+wu,vlfor 每条边(u,v)如果du!=+且dvdu+wu,v则存在负权回路9学堂A时间复杂度时间复杂度l算法复杂度为O(VE)其中V=顶点数，E=边数l我们知道Dijkstra的算法复杂度是O(V2)，经过优化的Dijkstra算法可以达到O(V+E)logE)l所以Bellman-Ford算法并不比它快，但实际上Bellman-Ford算法也是可以优化的10学堂ABellman-Ford算法的优化算法的优化l在没有负权回路的时候，至多进行n-1次松弛操作会得到解，但实际上可能不到n-1此松弛操作就得到最优解了l可以在每一轮松弛的时候判断是否松弛成功，如果所有的边都没有松弛的话，说明Bellman-Ford算法已经可以结束了11学堂A进一步的优化进一步的优化SPFA算法算法lSPFA=Shortest Path Faster Algorithml也即Bellman-Ford算法的队列优化，这里的队列可以用双向队列，也可以两个普通队列l初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。12学堂ASPFA算法的效率算法的效率l时间复杂度一般认为是O(kE)l其中k是一个较大的常数，不好估计，但是可以看出SPFA算法效率应当是很高的l经验表明Dijkstra算法的堆优化要比SPFA快，但SPFA比普通的Dijkstra算法快。而SPFA算法可以处理负权的问题，而且比Dijkstra算法的堆优化的代码要容易实现，因此SPFA是一个很好的算法。13学堂AExerciselPOJ 1511 Invitation Cards 可以用SPFA算法lPOJ =http:/14学堂A差分约束系统差分约束系统lX0=0lX0-X1=-1lX1-X2=-5lX2-X3=-3l求X1,X2,X3最小值lX1=1,X2=6,X3=9l求解差分不等式组有什么好的方法吗？15学堂A与与Bellman-Ford算法对比算法对比l前面用到过Distv=-wu,vl这与前面的不等式约束Xi-Xj=-k很类似，因此可以做如下转化：l如果存在约束条件Xi-Xj=-k，则建立一条边由i指向j，权值为k，这样就把差分约束系统问题转化为最短路径问题了，然后利用Bellman-Ford算法求解16学堂A与与Bellman-Ford算法对比算法对比l差分不等式组可能是没有解的，这实际上就对应了Bellman-Ford求解存在负权回路l根据具体情况，有的时候要求的是单源最长路径，道理是一样的17学堂APOJ 1201 Intervalsl输入数据l5l3 7 3l8 10 3l6 8 1l1 3 1l10 11 1l含义l有5组约束条件（至多50000）l区间3,7上至少有3个点l区间8,10上至少有3个点l区间6,8上至少有1个点l区间1,3上至少有1个点l区间10,11上至少有1个点l在区间0,50000上面有一些整点18学堂A问题的转化问题的转化l问题要求输出至少有多少个整点l如果用数组Si表示在0,i这个区间上面有多少个点，则题中输入数据ai,bi,ci可以表示为Sbi-Sai-1=cil除此之外还有隐含条件：Si+1-Si=0Si+1-Si=0lSi-1-Si=-ti也即Si=sum（实际上是=）lSi-Sj=Ri ij 且 i=j+8 mod 24lSi-Sj=Ri-sum ij 且 i=j+8 mod 2421学堂A进一步优化进一步优化l在上述不等式组中存在一个未知量sum，我们可以从小到大枚举sum的取值然后当Bellman-Ford没有发现负权回路的时候输出suml或者可以进一步优化，使用二分法枚举sum22学堂AThank you for your attentionAny questions please contact 05数学试点班 刁瑞NKOJ ID：doraemonok dorajudgehttp:/23学堂A