作者netsphere (再一次重來...)
看板Prob_Solve
標題Re: [問題] Floyd演算法的一個題目
時間Mon Aug 4 21:26:41 2008
※ 引述《netsphere (再一次重來...)》之銘言：
: ※ 引述《netsphere (再一次重來...)》之銘言：
: : 有點懶的算~ 叫程式幫你算吧 http://rafb.net/p/zgvUbv26.html
: : 其實我也有個問題要問 >///<
: : 遞迴式: distk(i,j)=Min(distk-1(i,j),distk-1(i, k)+distk-1(k, j))
: : 直接用遞迴式定義來寫是 O(n^4) 我的程式就是.....
: : 為什麼可以壓到O(n^3) 是那裡偷吃步了?
: 不懂怎麼證明.....Orz
: 先說一下 我對Dn的定義 Dn是表從i走n步到j的最短距離的矩陣Mij
: 後來想了一下能壓到 O(n^3) 是因為直接建立 Dn-1 的矩陣
: 偷吃了建立 D1 D2 ....Dn-2 的時間
: 如果一般人照觀念寫出來應該都是O(n^4) XD
我重看了一次 Floyd-Warshall algorithm 原來我從觀念上就錯了 ......Orz
不過往好處想 我發明了 Netsphere All-Pairs Shortest Path algorithm for (N^4) XD
謝謝參與討論的各位 Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.84.152