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.
|
