SPA个人总结

时间：2021-12-14 10:47:41 工作总结我要投稿

SPA个人总结

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

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

SPA个人总结

Dijkstra(G,w,s)

(1).initialize 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).for 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 2.Bellman-Ford

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

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

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//这就是检查是否存在负权回路。

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

return false return true 3.SPFA：shortest path faster algorithm

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

SPFA(G,w,s)

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

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

(3).while 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

4.Floyd-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.

【SPA个人总结】相关文章：

什么是水疗spa01-17

男子养生spa新时尚：男人的SPA保健养生方法01-18

SPA员工辞职书08-26