SPA个人总结

SPA个人总结范文 SPA个人总结范文

SPA个人总结2010-12-1013：201.Dijkstra

单源，带权有向图，不能有负权回路，也不能有负权边，复杂度为O(n^2)，贪心思想(每次选出一个最小路径节点，并用此来relax别的尚未选出的节点)，具体如下所述： Dijkstra(G,w,s)

(1).initializearraydtobethedistancebetweensandotherverticle,declareboolarrayusedtoflagiftheverticleischosenout,andusedistobefalseatfirst,exceptused[s]=1.

(2).foreachverticleinthegraphchoosetheshortestverticlev(edge)inarrayd used[v]=1；

withvtorelaxotherverticlewhichhasn'tbeen'used'inthegraph//hereisaprocessofloop2.Bellman-Ford

单源，带权有向图，可以存在负权回路(算法能给找出来，如果有的话),复杂度为O(ne),其想法如下：

1 / 3

其实就是对每条边进行|V|-1次Relax操作，然后在此基础上检查是否是存在负权回路，SPA个人总结。 forifrom1tov-1//求最小过程

foreachedge(u,v)inthegraphrelax(u,v,w)

foreachedge(u,v)inthegraph//这就是检查是否存在负权回路，工作总结《SPA个人总结》。 doif(d[v]d[u]+w)

returnfalsereturntrue3.SPFA：shortestpathfasteralgorithm 单源，带权有向图，复杂度O(2e),用top排序确定是否存在负权回路，不存在时(即允许负权边，不允许负权回路)，其想法如下(逐渐松弛的思想，若v松弛有效，则将其让入队列，以松弛别的节点)： SPFA(G,w,s)

(1).initializearraydtobethedistancebetweensandotherverticle

(2).declarequeueqtocontainverticle,andfirstinitializeitwiths.

(3).whileqisnotemptypopthefirstelementofqtou foreachvbelongsadj[u] tmp=d[v] relax(u,v,w)

checkif(d[v]！=tmp&&visnotinq)

2 / 3

pushvintoq 4.Floyd-Warshall

计算图中任意点到任意点之间的距离，是一种dp方案，复杂度为O(n^3)，允许负权边存在，但是不允许负权路径存在，其想法如下： 设图G中的顶点为V={1,2,.,n},对于任一对顶点(i,j)belongstoV,考查从i到j并且中间节点均属于节点子集合{1,2.k}的`所有路径，设其中p为一个最小权值路径(设p是简单的)。Floyd-Warshall算法利用的便是路径p与i到j之间的最短路径(由于路径p上的节点集合均属于{1,2,.,k})之间的联系。这一联系依赖于k是否是路径p上的中间节点。

(1)节点k(k是i到j之间路径的节点子集合里的最大编号节点)在路径p上，则d[i][j]=d[i][k]+d[k][j],其中i到k属于路径p1，k到j属于路径p2。

(2)节点k(k是i到j之间路径的节点子集合里的最大编号节点)不在路径p上，则往下考虑最大编号节点k-1。 当然这里的初始条件d[i][j]=w(i,j)whenk=0.

3 / 3