SPA个人总结范文

SPA个人总结

时间：2021-08-31

SPA个人总结范文

　　SPA个人总结范文

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

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

　　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操作，然后在此基础上检查是否是存在负权回路，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 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个人总结范文】相关文章：