《短路算法之spfa》ppt课件

《《短路算法之spfa》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SPFA/ShortestPathFasterAlgorithmBellman-FordBellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛（原文是这么写的，为什么要叫松弛，争议很大），每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。RelaxationRELAX(u,v)ifdis[v]>dis[u]+w(u,v)thendis[v]=dis[u]+w(u,v);//π[v]=u;Bellman-FordBELLMAN-FORDfori=1to

2、V

3、-1d

4、oforeveryedge(u,v)inEdoRELAX(u,v);//O(VE)队列优化我们用数组dis记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。队列基本操作ENQUEUE(Q,v)tail++;Q[tail]=v;DEQUEUE(Q)head++;DEQ

5、UEUE=Q[head];EMPTY(Q)returnhead>=tail;SPFASPFAINITIALIZE;ENQUEUE(Q,s);whilenotEMPTY(Q)u=DEQUEUE(Q);foreveryvertexvinadj[u]doifdis[v]>dis[u]+w(u,v)dis[v]=dis[u]+w(u,v);//π[v]=uifnotvinQENQUEUE(Q,s);//O(kE)循环队列ENQUEUE(Q,v)tail=(tail+1)modlen;Q[tail]=v;DEQUEUE(Q)head=(head+1)modlen;DEQU

6、EUE=Q[head];EMPTY(Q)returnhead=tail;