作者yin0416 (冷色鉛筆)
看板Fortran
標題Re: [問題] 小題目：各點之間的最小連結步數
時間Wed Dec 9 11:00:38 2009
關於最外層迴圈的順序問題，我的發現是，
找出正確路徑長的順序不只一種，
以 V4--V5--V1--V2--V3 為例，找出V4到V3的距離，
K由1~5依序代入的話，
A.會先找出V5--V1--V2的長度，
B.再找出V5--(V1)--V2--V3，
C.最後找出V4--(V5)--(V1)--V2--V3
找出的順序是A-->B-->C，
但如果將順序反過來的話，即C-->B-->A時，
是無法找出正確路徑長的，
現在我們將K由5~1依次代入，
D.先找出V4--V5--V1
E.再找出V1--V2--V3
F.最後再找V4--(V5)--V1--(V2)--V3
結論，不只一種拼出路徑長的方式！
謝謝各位的耐心觀看 ＞＿＜
: : 整個演算法寫出來只需要三層迴圈
: : 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
--
◥ ◢◥◣ △ㄑ◤◢◥ ／
◤〝 ▇▇ 〞◥＼
◢ㄑ◥◣\ ◣ / \ ◣ \
◤〝／／ ＼＼〞◣/
◥◥◤◤◤◥◤◥◢ !◣ ◤◤◤)◥◥ ◤! ／＼
／＼
◣◤ 〒 〒 ◥◢ ◣◤ ● ● ◥◤ ──
／
◣ —lm ◢ ◥◣"" v ""◢◤
╱
▇ ◣ ※╲ ◣
◢◥ ◤◣ ψg80046
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.128.128.158
1F：→ yin0416:如何嚴格證明之～～～～苦腦中～～～～～～ 12/09 12:37
2F：→ mantour:其實我原文中就寫到證明的邏輯了 12/09 19:50
3F：→ mantour:我覺得你沒有看懂這個演算法的精神耶 12/09 19:51