推 cakeboy:什麼是DPS阿 02/09 22:41
推 ract1436:DFS嗎? 02/09 22:47
※ 編輯: johnyne 來自: 1.161.193.164 (02/09 22:48)
推 hswayne:感謝close大 02/09 23:11
※ 引述《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