這個問題是典型的dynamic programming的例子 基本上可以直接套用floyd最短路徑演算法 就演算法的精神說明一下 一開始用一個矩陣D表示節點的相鄰性 D(i,i) = 0 若vi,vj之間有連結，則D(i,j)=1 若沒有連結 D(i,j) = Inf (Inf 為自設的常數，比任二點可能的最大步數大) 此時D(i,j)表示了vi,vj直接相連的步數 接著考慮從vi走到vj，中間可以經過v1的最少步數 如果經過v1的步數比本來直接走短，就把D(i,j)重設為新路徑的步數 也就是說對所有的i,j if( D(i,1)+D(1,j) .lt. D(i,j)) then D(i,j) = D(i,1) + D(1,j) end if 再來考慮vi,vj中間可經過v1,v2的最少步數 這裡有一點tricky的地方是，我們不需要真的去算所有經過v1或v2的組合 只要分成二點來考慮就可以了的大小就可以了 1) 由vi到vj 可經可不經v1 但 不經v2 也不經過其他點 的最小步數 2) 由vi到vj 可經可不經v1 但 必須經過 v2 不經過其他點 的最小步數 只要比較這二個數值中比較小的就是由vi到vj 可經可不經v1,v2 的最少步數 其中 1)前面已經算過了，就是 目前的D(i,j) 而2)呢？ 可以想一想，如果有一條最短的路線從 vi 經過 v2 到 vj 中間可經可不經v1 但不可經過其他點 則其中由vi到v2和由v2到vj這二段分別一定也是走可經可不經v1 而不經其他點的最短路徑 也就是 2) = D(i,2) + D(2,j) 因此假如對所有i,j再進行一次重設 if( D(i,2)+D(2,j) .lt. D(i,j)) then D(i,j) = D(i,2) + D(2,j) end if 就得到任二點之間 可經可不經 v1,v2 ，但不經其他點的最短步數 重複這個動作 就可以得到任二點之間，可經可不經其他所有點 的最短步數 也就是我們要的答案 整個演算法寫出來只需要三層迴圈 do k=1,N do j=1,N do i=1,N if (D(i,k)+D(k,j) .lt. D(i,j)) then D(i,j) = D(i,k) + D(k,j) end if end do end do end do 時間複雜度為O(N^3) 其中由於連結沒有方向性，因此D是對稱的，實際上只需計算上三角的部份即可 所以還可以再修改節省一點時間 打了半天好像還是講得不是很清楚 不過只要把演算法的名字丟到google應該就可以找到更詳細的說明 希望對原PO有幫助 也希望我有寫錯的地方大家可以幫我指出來 ※ 引述《yin0416 (冷色鉛筆)》之銘言： : 假設有Ｎ個點，每個點相互之間有些有連結，有些沒有連結。 : 給你一個Ｎ乘Ｎ的矩陣，代表每個點相互之間連結的有或無。 : 請算出每個點與點之間的最小連結步數， : 例如點１與點２有連結，點２與點３之間有連結，而點１與點３之間沒有直接連結， : 則點１與點３之間的最小連結步數即為２步。 : 老師並不要求我寫出來，所以我不是為了應付作業而來發問的。 : 這個程式的結構我想了很久，但沒有想出來。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.213.158