a*******n 发帖数: 64 | 1 Given the Dijkstra's algorithm (finding the shortest path) and a acylic
graph, how can we modify the graph to find the longest path?
Didn't think of any good answer to this one? Anyone has an idea? |
S**I 发帖数: 15689 | 2 This is a NP-complete problem.
【在 a*******n 的大作中提到】 : Given the Dijkstra's algorithm (finding the shortest path) and a acylic : graph, how can we modify the graph to find the longest path? : Didn't think of any good answer to this one? Anyone has an idea?
|
f*****e 发帖数: 2992 | 3 不是,和求binary tree任意两点距离差不多。
【在 S**I 的大作中提到】 : This is a NP-complete problem.
|
S**I 发帖数: 15689 | 4 Didn't notice "acyclic";both longest path and shortest path on a directed
acyclic graph can be solved in linear time by using topological ordering.
Dijkstra's algorithm is not necessary.
【在 f*****e 的大作中提到】 : 不是,和求binary tree任意两点距离差不多。
|
a*******n 发帖数: 64 | 5 能展开说说吗?
这个问题主要不是怎么用topo sorting and DP去找longest path
而是问如果给你找到shortest path的算法,问怎么改graph去找longest
【在 f*****e 的大作中提到】 : 不是,和求binary tree任意两点距离差不多。
|
a*******n 发帖数: 64 | 6 Dijkastra's algorithm doesn't work on graph with neg weights
in
Run
【在 S**I 的大作中提到】 : Didn't notice "acyclic";both longest path and shortest path on a directed : acyclic graph can be solved in linear time by using topological ordering. : Dijkstra's algorithm is not necessary.
|