作者pttworld (批踢踢世界)
看板Prob_Solve
标题Re: [问题] 最短路径问题
时间Fri Aug 12 00:25:18 2016
※ 引述《noodleT (面T)》之铭言：
: http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d062
: 题目如上面连结。
: 我的做法是先求出任两点间的最短路径值，
: 接着利用贪婪法决定下一个拜访(最近)的城市。
: 但如果离起点(当下位置)最近的有两个以上，
: 则把这些路径都测试过一遍。
: 虽然有通过测验，但这种作法是正确的吗？
: 还是运气好罢了？
: 会提出这问题是因为想到 TSP 无法用贪婪解。
本题使用Floyd Warshall後Depth First Search得解。
着名最短路径两种演算法：Dijkstra及Floyd Warshall对应单点至全图及全点全图。
（如果跑n次Dijkstra也可以）
得到所有点单对单的最短距离後进行n-1次（扣掉起点）的最短加总。
因为最短可能不只一组点对，使用DFS展开。
如没有记忆体量及执行时间限制可以只使用BFS。
--
排了二万多顺位注册的队，首发
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 115.43.36.13
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1470932721.A.70A.html