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个人总结范文】相关文章:

1.心灵Spa For Mind美文随笔

2.SPA员工辞职报告

3.个人总结范文

4.个人总结及个人计划的范文

5.个人安全反思总结范文

6.医院转正个人总结范文

7.保安转正个人总结范文

8.医学个人总结范文大全