作者tkcn (小安)
看板Prob_Solve
标题Re: [问题] longest path
时间Mon Nov 1 01:02:20 2010
※ 引述《CMturtle (杰尼龟)》之铭言：
: 是说~~~一般最短路的演算法为什麽不能处理最长路阿？？
因为最短路径演算法是使用 Dynamic Programming，
而 DP 能解的问题必须具备 optimal substructure 特性。
以最短路径来说，一条最短路径随意拆成两段，
这两段也会是最短路径 (否则我们大可把原来路径对应的一段替换为现在更短的这条)
但是最长路径并没有这种特性，以 A 到 B 来说，
即使我们能找到 A 到 C 的最长路径以及 C 到 B 的最长路径，
把这两段合起来，却不见得能得到 A 到 B 的最长路径，
因为很可能有重复的 vertex。 (违反 simple path 定义)
: 我的想法是
: 在无相图中会出现正环的关系
: 但是如果再「有向无环图」（DAG）中
: 是不是就可以套用最短路的算法来写最长路？
单就这问题，我想你看了上面的说明应该可以自己回答，所以我就不给答案了。
不过，在 DAG 中要求最短路径或最长路径，有更简单的 DP 作法能达成。
: 而bellman-ford & SPFA应该也可以再有向图中来判断正环罗？？
如果你把 edge 的 weight 全部正负交换，然後侦测 negtive cycle，
或着修改 relax 改成纪录较长的路径，我想大概也能判断的出来。
不过，简单的 DFS/BFS 就能找出 positive cycle 了，
所以应该是没什麽必要用 bellman-ford。
--
◤ ◥ ◢ ◣
T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到问题，用SoftICE就对了！
╰ ∕皿﹨ ◥皿◤ ╯
◥█◤◢ ◥ ︶◤
Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen
ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.231
1F：推 CMturtle:谢谢你们>"< 清大的学长耶~~ 11/01 01:09
2F：→ yoco315:113 发文, 112 跟 114 回答, 太温馨了 QQ 11/01 06:20
3F：推 yauhh:那如果是将A-C,C-B的longest path以union方式衔接,可以解吗? 11/01 09:25
4F：推 ledia:A-D-C, C-D-B 是 longest path, 要怎麽 union ? 11/01 09:52
5F：→ yauhh:这你不用管. 11/01 10:04
※ 编辑: tkcn 来自: 140.114.78.231 (11/01 13:59)
6F：推 LPH66:或许A-B的longest path其实是A-E-B 而E却不在A-C C-B当中 11/01 17:16
7F：推 ledia:喔喔, y 版友真是伟大 m(_ _)m 11/02 10:03
8F：推 zerodevil:y大师说的是 受教了 11/02 15:56