SPA個人總結(jié)范文
SPA個人總結(jié)范文
SPA個人總結(jié)2010-12-10 13：201.Dijkstra
單源，帶權(quán)有向圖，不能有負(fù)權(quán)回路，也不能有負(fù)權(quán)邊，復(fù)雜度為O(n^2)，貪心思想(每次選出一個最小路徑節(jié)點(diǎn)，并用此來relax別的尚未選出的節(jié)點(diǎn))，具體如下所述：
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
單源，帶權(quán)有向圖，可以存在負(fù)權(quán)回路(算法能給找出來，如果有的話),復(fù)雜度為O(ne),其想法如下：
其實(shí)就是對每條邊進(jìn)行|V|-1次Relax操作，然后在此基礎(chǔ)上檢查是否是存在負(fù)權(quán)回路，SPA個人總結(jié)。
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//這就是檢查是否存在負(fù)權(quán)回路，工作總結(jié)《SPA個人總結(jié)》。
do if(d[v]d[u]+w)
return false return true 3.SPFA：shortest path faster algorithm
單源，帶權(quán)有向圖，復(fù)雜度O(2e),用top排序確定是否存在負(fù)權(quán)回路，不存在時(即允許負(fù)權(quán)邊，不允許負(fù)權(quán)回路)，其想法如下(逐漸松弛的思想，若v松弛有效，則將其讓入隊(duì)列，以松弛別的'節(jié)點(diǎn))：
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
計算圖中任意點(diǎn)到任意點(diǎn)之間的距離，是一種dp方案，復(fù)雜度為O(n^3)，允許負(fù)權(quán)邊存在，但是不允許負(fù)權(quán)路徑存在，其想法如下：
設(shè)圖G中的頂點(diǎn)為V={1,2,.,n},對于任一對頂點(diǎn)(i,j)belongs to V,考查從i到j(luò)并且中間節(jié)點(diǎn)均屬于節(jié)點(diǎn)子集合{1,2.k}的所有路徑，設(shè)其中p為一個最小權(quán)值路徑(設(shè)p是簡單的)。Floyd-Warshall算法利用的便是路徑p與i到j(luò)之間的最短路徑(由于路徑p上的節(jié)點(diǎn)集合均屬于{1,2,.,k})之間的聯(lián)系。這一聯(lián)系依賴于k是否是路徑p上的中間節(jié)點(diǎn)。
(1)節(jié)點(diǎn)k(k是i到j(luò)之間路徑的節(jié)點(diǎn)子集合里的最大編號節(jié)點(diǎn))在路徑p上，則d[i][j]=d[i][k]+d[k][j],其中i到k屬于路徑p1，k到j(luò)屬于路徑p2。
(2)節(jié)點(diǎn)k(k是i到j(luò)之間路徑的節(jié)點(diǎn)子集合里的最大編號節(jié)點(diǎn))不在路徑p上，則往下考慮最大編號節(jié)點(diǎn)k-1。
當(dāng)然這里的初始條件d[i][j]=w(i,j)when k=0.
【SPA個人總結(jié)】相關(guān)文章：
心靈Spa For Mind美文隨筆06-29
SPA員工辭職報告02-27
某SPA健身會開業(yè)慶典的策劃方案07-07
身體SPA護(hù)膚系列廣告詞有哪些06-12
個人研修總結(jié)個人總結(jié)03-16