SPA個人總結範文
SPA個人總結2010-12-10 13:stra
單源,帶權有向圖,不能有負權迴路,也不能有負權邊,複雜度爲O(n^2),貪心思想(每次選出一個最小路徑節點,並用此來relax別的尚未選出的節點),具體如下所述:
Dijkstra(G,w,s)
(1)ialize 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) 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 man-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 :shortest path faster algorithm
單源,帶權有向圖,複雜度O(2e),用top排序確定是否存在負權迴路,不存在時(即允許負權邊,不允許負權迴路),其想法如下(逐漸鬆弛的思想,若v鬆弛有效,則將其讓入隊列,以鬆弛別的節點):
SPFA(G,w,s)
(1)ialize array dto be the distance between sand other verticle
(2)are queue qto contain verticle,and first initialize it with s.
(3)e 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
d-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.