Re: [問題] 小題目：各點之間的最小連結步數

看板Fortran作者mantour (朱子)時間15年前 (2009/11/07 00:35)推噓4(4推 0噓 1→)

留言5則, 2人參與討論串3/6 (看更多)

這個問題是典型的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