Re: [理工] [algo] 99中央第六題

看板Grad-ProbAsk作者johnyne (close 醬)時間15年前 (2011/02/09 22:38)推噓3(3推 0噓 0→)

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

※ 引述《hswayne (>酷炫<小豪)》之銘言： : 附個連結: : http://ppt.cc/9(33 : 有人有比較好的想法嗎!? : 有請高手解惑~ 這題的hint就是這個圖是tree 也就是說所有的ALL PAIR SHORTEST PATH的結果相當於路徑長(因為樹任二點只有一種path,則此path就是答案) 觀念:利用DFS or BFS 找出 spanning tree 則可以知道某一個點到所有點的最短路長每一個點花O(V+E) 做N次(N個點) 知道TIME為:O(N*(V+E)) 但是E=N-1 代進去答案為O(N^2) 所以虛擬碼只要對DFS 或BFS進行修改即可有錯請指教謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.161.193.164

推

cakeboy

02/09 22:41, , 1^F

02/09 22:41, 1^F

推

ract1436

02/09 22:47, , 2^F

02/09 22:47, 2^F

※ 編輯: johnyne 來自: 1.161.193.164 (02/09 22:48)

推

hswayne

02/09 23:11, , 3^F