SPA個人總結

單源，帶權有向圖，不能有負權回路，也不能有負權邊，復雜度為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操作，然后在此基礎上檢查是否是存在負權回路。

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//這就是檢查是否存在負權回路。

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個人總結】相關文章：

做SPA的注意事項07-25

spa (n.) 溫泉浴場05-04

電工個人轉正總結_個人總結06-03

個人計劃個人總結11-26

個人總結06-02

個人的總結11-10

初中教師的個人總結個人總結初中教師個人總結10-21

個人期末總結 -個人工作總結03-13

公司個人總結 -個人工作總結12-15

校長個人總結06-21