浅谈bellmanford

Bellman-Ford算法与SPFA算法单源最短路径问题单源最短路径=SingleSourceShortestPath，即在有向图（或无向图）中求解给定点到其他点之间的最短距离我们已知的方法是……XXX讲的Dijkstra算法但是…………Dijkstra算法的局限性如果边权为负值，Dijkstra算法还正确吗？求解右图A至其他点的最短距离算法步骤：1）标记点A2）D[A,C]=2最小，标记点C3）D[A,B]=3最小，标记点B结束但是实际上A到C点的最短距离为1（A到B到C）ABC23-2Dijkstra算法的局限性下图中，A至F的最短路径长度是多少？ABCDEF11-1-1-1-1Dijkstra算法的局限性由于B,C,D,E构成了负权回路，所以A到F的最小距离为负无穷……但是…………Dijkstra算法的局限性如果利用Dijkstra算法求解，结果为……标记点A，D[B]=-1，标记点BD[C]=0，标记点CD[D]=-1，标记点DD[E]=-2，标记点ED[F]=-1，标记点F所求得的距离并不是最短的ABCDEF11-1-1-1-1错误结果的原因Dijkstra的缺陷就在于它不能处理负权回路：Dijkstra对于标记过的点就不再进行更新了，所以即使有负权导致最短距离的改变也不会重新计算已经计算过的结果我们需要新的算法——Bellman-FordBellman-Ford算法思想Bellman-Ford算法基于动态规划，反复用已有的边来更新最短距离Bellman-Ford算法的核心思想——松弛那么何为松弛操作呢……其实我们之前提到过……松弛操作若F[u]和F[v]应当满足F[v]=F[u]+w[u,v]则F[V]的值更新为F[U]+w[u,v]反复的利用上式对F数组进行松弛，如果没有负权回路的话，应当会在有限次松弛之后结束。那么这个次数应该是多少？简单点说……考虑对每条边进行1次松弛的时候，得到的实际上是至多经过0个点的最短路径，对每条边进行两次松弛的时候得到的是至多经过1个点的最短路径，……如果没有负权回路，那么任意两点间的最短路径至多经过n-2个点，因此经过n-1次松弛操作后应当可以得到最短路径如果有负权回路，那么第n次松弛操作仍然会成功，这时，最短路径为-∞Bellman-Ford算法流程1,.初始化：将除源点外的所有顶点的最短距离估计值f[v]←+∞,f[s]←0;2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[v]中。1235467编号01234距离02599Bellman-Ford算法最简单的形式……Fori:=1tondoD[i]:=maxlongint;D[s]:=0//出发点为sfork:=1ton-1doforj:=1toEdoifd[e[j,1]]d[e[j,2]+w[j]thend[e[j,1]]=d[e[j,2]]+w[j];Flag:=true;fork:=1toEdoifd[e[k,1]]d[e[k,2]]+w[k]thenflag:=false;Ifflagthenwrite(d[n])elsewrite(‘error’);（E[i,1]，E[i,2]表示第i条边两个端点,w[i]表示第i条边得权值。）时间复杂度算法复杂度为O(VE)其中V=顶点数，E=边数我们知道Dijkstra的算法复杂度是O(V^2)，所以Bellman-Ford算法并不比它快，但实际上Bellman-Ford算法也是可以优化的Bellman-ford算法优化Bellman-ford算法有一个小优化：每次松弛先设一个变量flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无比要的松弛于是出现了用队列进行了优化的SPFA算法进一步的优化——SPFA算法SPFA=ShortestPathFasterAlgorithm即Bellman-Ford算法的队列优化实现方法：1、建立一个队列，初始时队列里只有起始点，在建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。2、执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空3、判断有无负环：如果某个点进入队列的次数超过N次则存在负环(存在负环则无最短路径,如果有负环则会无限松弛,而一个带n个点的图至多松弛n-1次)路径的记录在一幅图中，我们仅仅知道结点A到结点E的最短路径长度是73，有时候意义不大。这附图如果是地图的模型的话，在算出最短路径长度后，我们总要说明“怎么走”才算真正解决了问题。如何在计算过程中记录下来最短路径是怎么走的，并在最后将它输出呢？建立一个Path数组，Path[i]表示从S到i的最短路径中，结点i之前的结点的编号。注意，是“之前”，不是“之后”。我们只需要在借助结点u对结点v进行松弛的同时，标记下Path[v]=u，记录的工作就完成了。算法执行到第五步后，队空，算法结束。源点V0到V1的最短路径为2，到V2的最短路径为5，到V3的最短路径为9，到V4的最短路径为9，结果显然是正确的。小小的总结一下……SPFA在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。具体过程（假定不含有负权回路）constmaxp=10000;{最大结点数}var{变量定义}p,c,s,t:longint;{p,结点数;c,边数;s:起点;t:终点}a,b:array[1..maxp,0..maxp]oflongint;{a[x,y]存x,y之间边的权;b[x,c]存与x相连的第c个边的另一个结点y}d:array[1..2*maxp]ofinteger;{队列}v:array[1..maxp]ofboolean;{是否入队的标记}dist:array[1..maxp]oflongint;{到起点的最短路}head,tail:longint;{队首/队尾指针}具体过程（假定不含有负权回路）procedureinit;vari,x,y,z:longint;beginread(p,c);fori:=1tocdobeginreadln(x,y,z);{x,y:一条边的两个结点;z:这条边的权值}inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z;{b[x,0]：以x为一个结点的边的条数}end;具体过程（假定不含有负权回路）procedurespfa;{SPFA}vari,j,now,sum:longint;beginforj:=1tondodist[j]:=maxlongint;dist[s]:=0;v[1]:=true;now:=1;{队列的初始状态,s为起点}head:=1;tail:=1;whilehead=taildo{队列不空}beginnow:=d[head];{取队首元素}fori:=1tondoifdist[i]dist[now]+a[now,i]thenbegindist[i]:=dist[now]+a[now,i];{修改最短路}ifnotv[i]then{扩展结点入队}begintail:=tail+1;d[tail]:=i;v[i]:=true;end;end;v[now]:=false;{释放结点，一定要释放掉，因为这节点有可能下次用来松弛其它节点}head:=head+1;{出队}end;end;SPFA算法的效率时间复杂度一般认为是O(kE)其中可以证明k一般小于等于2。可以看出SPFA算法效率应当是很高的与其他算法的比较与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。经验表明Dijkstra算法的堆优化要比SPFA快，但SPFA一般比普通的Dijkstra算法快。而SPFA算法可以处理负权的问题，而且比Dijkstra算法的堆优化的代码要容易实现，因此SPFA还是一个很好的算法。Spfa的进一步优化前向星不要把前向星想成什么高深莫测的东西……它其实就是一种类似邻接表的紧缩存储形式。为什么叫前向星？因为它是将边按照前端点排序，并用一个数组point[i]记录端点i第一次以左端点出现的位置。这样，我们就能用O(E)的空间复杂度存储下一个邻接表，而避免了链表或N^2的庞大空间消耗。边编号1234567起点0011234终点1442342权21073456012345135678Point数组在数组point中，其元素个数比图的节点数多1(即共有v+1个节点)，且一定有point[1]=1，point[v+1]=E+1。对于节点i，其对应的边存放在边信息数组的位置区间为[point[i],point[i+1]-1]如果point[i]=point[i+1]，则节点没有出边。“边信息数组”实际上相当于将边有序存放。或者说是是边被按初始点编号后有序存放而组成的表，数组point记录每个节点出发的边的起始编号。通常用在点的数目太多，或两点之间有多条边的时候。一般在别的数据结构不能使用的时候才考虑用前向星。vara(起点),b（终点）,e（权值）:array[1..1000]oflongint;//边信息数组v:array[1..2000]ofboolean;//用来标记某个点是否以入队的数组q(队),d（到某点的最短距离）,f(上文中的point数组):array[1..2001]oflongint;n,m,i,s,t:longint;前向星算法求S到T的最短路Beginreadln(n,m);fori:=1tomdoreadln(a[i],b[i],e[i]);qsort(1,m);fori:=1tomdoiff[a[i]]=0thenf[a[i]]:=i;f[n+1]:=m+1;fori:=ndownto1doiff[i]=0thenf[i]:=f[i+1];readln(s,t);spfa(s);writeln(d[t]);end.procedurespfa(s:longint);vari,k,l,t:longin