SPA个人总结

SPA个人总结(总3页)

--本页仅作预览文档封面，使用时请删除本页--

SPA个人总结

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

SPA个人总结2010-12-1013：

单源，带权有向图，不能有负权回路，也不能有负权边，复杂度为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'inthegraphnitializearraydtobethedistancebetweensandotherverticle

2

(2).declarequeueqtocontainverticle,andfirstinitializeitwiths.

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

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

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

设图G中的顶点为V={1,2,.,n},对于任一对顶点

(i,j)belongstoV,考查从i到j并且中间节点均属于节点子集合{1,}的`所有路径，设其中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。

3

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

4