Re: [問題] Floyd演算法的一個題目

[netsphere (再一次重來...)]

:      如圖:http://www.badongo.com/pic/4102668

   有點懶的算~ 叫程式幫你算吧 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)  是那裡偷吃步了?


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.165.198.173
推 s0908744:不好意思 那個...程式..不會RUN.
→ netsphere:五樓交給你了
→ LPH66:最外層的t就是中介點  所以不必再一層u  正確性由DP保證
推 scan33scan33:1F去下載devC run吧！google一下就可以找到用法了
→ scan33scan33:正確性簡單的induction on t得證
→ scan33scan33:on k說錯，然後證明的這個方向就跟程式寫法一樣。
→ scan33scan33:就很自然!?(偷偷當五樓XD)