SPA个人总结范文

SPA个人总结范文

SPA个人总结2010-12-10 13：stra

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

Dijkstra(G,w,s)

(1)ialize array dto be the distance between sand other verticle,declare bool array used to flag if the verticle is chosen out,and used is to be false at first,except used[s]=1.

(2) each verticle in the graph choose the shortest verticle v(edge)in array d

used[v]=1；

with vto relax other verticle which hasn't been'used'in the graph//here is aprocess of loop man-Ford

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

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

for ifrom 1to v-1//求最小过程

for each edge(u,v)in the graph relax(u,v,w)

for each edge(u,v)in the graph//这就是检查是否存在负权回路，工作总结《SPA个人总结》。

do if(d[v]d[u]+w)

return false return true ：shortest path faster algorithm

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

SPFA(G,w,s)

(1)ialize array dto be the distance between sand other verticle

(2)are queue qto contain verticle,and first initialize it with s.

(3)e qis not empty pop the first element of qto u

for each vbelongs adj[u]

tmp=d[v]

relax(u,v,w)

check if(d[v]！=tmp&&v is not in q)

push vinto q

d-Warshall

计算图中任意点到任意点之间的距离，是一种dp方案，复杂度为O(n^3)，允许负权边存在，但是不允许负权路径存在，其想法如下：

设图G中的顶点为V={1,2,.,n},对于任一对顶点(i,j)belongs to V,考查从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)when k=0.