這個算法與prim算法類似，在第9-10行中做了什麼？

Question

我明白這個問題有點類似於在這個論壇上提出的另一個問題，但我的問題是一個具體問題，而另一個問題沒有提供答案。

我將引用的算法如下。我知道這個算法循環遍歷圖中的每個頂點並賦值爲無窮大。它也賦予集合V中的「s」爲0.我猜「s」是父節點？然後它創建一個集合「A」來存儲訪問節點。雖然該集合不包含集合「V」中的所有頂點，但它將選擇一個節點，其中最小值尚未在「A」中。然後它遍歷所有的頂點adj。到這個節點。它比較每個形容詞的價值。節點到（主節點的值+邊緣值）。然後它設置adj。節點到主節點+邊的值，如果adj的值。節點比它少。我的問題是，我們爲什麼要這樣做？什麼目的？

 

Algorithm (G, s) 
 
    for v in V:
 
     val[v] = infinity 
 
     val[s]= 0
 
    A = {} # A is a set
 
    while A != V:
 
     select vertex x not in A with minimum val[x]
 
     A = A /in {x}
 
     for each vertex y adjacent to x:
 
      if (val[x] + w(x, y)) less than val[y]:
 
       val[y] = val[x] + w(x, y)
 

Answer 1

這裏是一個小圖：

選擇一個作爲起始頂點小號，運行手工你的算法，並告訴我們VAL的內容陣列。如果您在此之後仍然有問題，我們將很樂意爲您提供幫助。