l*******r
发帖数: 322 | 1 图中两个节点之间的最短路径可以通过动态规划（dynamic programming）解决
那么下面的几个问题中，哪些同样可以用动态规划解决，哪些不能，哪些能用但不一定
是最优解决方案的呢？
1. 两个节点之间的次短路径
2. 两个节点之间的最短路径，但是两两节点间的路径“长度”可能为负数
3. 两个节点之间不含重复节点的最长路径
4. 某个节点集合到集合外的某节点的最短路径
i.e. shortestpath(S,t) = min[ shortestpath(s,t)] where s \in S, t \notin S
5. 最短路径的某种近似算法（只要有合理的bound就行） | h*******e
发帖数: 225 | 2 哪个都可以用dp，关键是复杂度。除了3，其他都有polynomial time算法。3是经典的
NPC问题。
notin S
【在 l*******r 的大作中提到】
: 图中两个节点之间的最短路径可以通过动态规划（dynamic programming）解决
: 那么下面的几个问题中，哪些同样可以用动态规划解决，哪些不能，哪些能用但不一定
: 是最优解决方案的呢？
: 1. 两个节点之间的次短路径
: 2. 两个节点之间的最短路径，但是两两节点间的路径“长度”可能为负数
: 3. 两个节点之间不含重复节点的最长路径
: 4. 某个节点集合到集合外的某节点的最短路径
: i.e. shortestpath(S,t) = min[ shortestpath(s,t)] where s \in S, t \notin S
: 5. 最短路径的某种近似算法（只要有合理的bound就行）
|
|
