看板 [ Prob_Solve ]
討論串[問題] Floyd演算法的一個題目
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] Floyd演算法的一個題目
推噓6(6推 0噓 6→)留言12則，0人參與, 最新作者s0908744 (抖抖)時間16年前 (2008/07/30 20:23), 編輯資訊
1
0
1
內容預覽:
大家好. 想請問關於 Floyd演算法 的一個題目. 明天是暑修期末考，老師有透漏這個題目但是沒有給解答.... 煩請順手幫幫忙嚕 感恩. 題目:請用Floyd演算法求出任兩頂點之間最短路徑. 如圖:http://www.badongo.com/pic/4102668. 公式: distk(i,j)
#2
Re: [問題] Floyd演算法的一個題目
推噓2(2推 0噓 5→)留言7則，0人參與, 最新作者netsphere (再一次重來...)時間16年前 (2008/07/30 22:30), 編輯資訊
1
0
2
內容預覽:
有點懶的算~ 叫程式幫你算吧 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) 我的
#3
Re: [問題] Floyd演算法的一個題目
推噓0(0推 0噓 3→)留言3則，0人參與, 最新作者netsphere (再一次重來...)時間16年前 (2008/08/03 22:22), 編輯資訊
1
0
2
內容預覽:
不懂怎麼證明.....Orz. 先說一下 我對Dn的定義 Dn是表從i走n步到j的最短距離的矩陣Mij. 後來想了一下能壓到 O(n^3) 是因為直接建立 Dn-1 的矩陣. 偷吃了建立 D1 D2 ....Dn-2 的時間. 如果一般人照觀念寫出來應該都是O(n^4) XD. --. ※ 發信站:
#4
Re: [問題] Floyd演算法的一個題目
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者netsphere (再一次重來...)時間16年前 (2008/08/04 21:26), 編輯資訊
0
0
1
內容預覽:
我重看了一次 Floyd-Warshall algorithm 原來我從觀念上就錯了 ......Orz. 不過往好處想 我發明了 Netsphere All-Pairs Shortest Path algorithm for (N^4) XD. 謝謝參與討論的各位 Orz. --. ※ 發信站:
首頁
上一頁
1
下一頁
尾頁