看板
[ Fortran ]
討論串[問題] 小題目：各點之間的最小連結步數
共 6 篇文章
內容預覽:
假設有Ｎ個點，每個點相互之間有些有連結，有些沒有連結。. 給你一個Ｎ乘Ｎ的矩陣，代表每個點相互之間連結的有或無。. 請算出每個點與點之間的最小連結步數，. 例如點１與點２有連結，點２與點３之間有連結，而點１與點３之間沒有直接連結，. 則點１與點３之間的最小連結步數即為２步。. 老師並不要求我寫出來，
(還有158個字)
內容預覽:
無聊亂寫的…. 假設有九個點，各點連接的情形如下. 1 : 3 5 7 9. 2 : 4 6. 3 : 1 6 8. 4 : 2 5 7. 5 : 1 4. 6 : 2 3 7 9. 7 : 1 4 6. 8 : 1 3. 9 : 1 6. 現在找點2連接到點9的路徑. 程式如下. 跑到第二層就有結
(還有1833個字)
內容預覽:
這個問題是典型的dynamic programming的例子. 基本上可以直接套用floyd最短路徑演算法. 就演算法的精神說明一下. 一開始用一個矩陣D表示節點的相鄰性. D(i,i) = 0. 若vi,vj之間有連結，則D(i,j)=1. 若沒有連結. D(i,j) = Inf (Inf 為自設
(還有996個字)
內容預覽:
首先非常感謝mantour大大的解釋：. 另外在此鄭重的向mantour道個歉，當天投水球問問題時，. 我的行為顯得突兀冒失....... 希望mantour大人大量不予計較。. 最後提出我對這個演算法的發現與疑問，. 當i,j,k任兩個為相同時，其路徑長 D(i,j) 不會產生任何改變，. 所以可
(還有814個字)
內容預覽:
關於最外層迴圈的順序問題，我的發現是，. 找出正確路徑長的順序不只一種，. 以 V4--V5--V1--V2--V3 為例，找出V4到V3的距離，. K由1~5依序代入的話，. A.會先找出V5--V1--V2的長度，. B.再找出V5--(V1)--V2--V3，. C.最後找出V4--(V5)-
(還有359個字)