作者st84514 (綜合水果武士)
看板Grad-ProbAsk
標題[理工] [演算法]證明BFS最短路徑問題!
時間Wed Dec 29 19:50:29 2010
若現在有ABCDE五個頂點之連通無向圖
假設現在要求A到E所經過的頂點數要最少是否用BFS?
若是的話應該怎求證?
BFS又是如何操作才可得到此結果?
想很久的問題懇請高手解答!謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.189.70
1F:→ master1x4:感覺像是shortest path問題? 12/29 20:29
2F:→ st84514:應該是...可是不知如何證明跟運作 12/30 09:44
3F:→ FRAXIS:數學歸納法吧.. 證明BFS找到的是最短路徑 12/30 17:53
4F:推 christianSK:會證明shortest path的話就沒什麼問題了吧 12/30 20:53
5F:→ christianSK:把各edge 的weight當成1就可以做了不是?! 12/30 20:54