[理工] [資結] 交大99資訊聯招

看板Grad-ProbAsk作者boy5548 (小YO)時間15年前 (2011/01/24 16:28)推噓1(1推 0噓 10→)

留言11則, 5人參與討論串1/1

Given a weighted graph and two vertices s and t, we want to find a longest path from s to t. Which of the following statements are WRONG about this problem? (i)This problem has a polynomial time algorithm. (ii)This problem can be solved by transforming it into shortest path problem. (iii)This problem can be solved by using Dynamic Programming. (iv)For a connected weighted graph the longest path has at least 3 edges. (v)For a graph with n vertices, if the longest path has n-1 edges,then it passes through each vertex exactly once. 答案是(i)(ii)(iv) 我的問題是第(iii)，我記得longest problem是NP-Complete吧?他可以用DP解嗎... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.27.122.17

→

jameschou

01/24 17:02, , 1^F

01/24 17:02, 1^F

→

jameschou

01/24 17:03, , 2^F

01/24 17:03, 2^F

推

cakeboy

01/24 17:54, , 3^F

01/24 17:54, 3^F