b*******e
发帖数: 217 | 1 A graph, find the shortest path between S and T with the number of edges = K
.
What is the complexity of your algorithm. | l***i
发帖数: 1309 | 2 这个好阴险阿，如果K = |V|，
this is hamitonian path problem and is hence NP-hard, what is your algorithm
's complexity
Here I assume by path you mean a sequence of edges with no repeated vertex. | b*******e
发帖数: 217 | 3 this is a DP problem.
SPath(S, V, K) = Min(SPath(S, Parents of V, K-1) + W)
this is called shortest reliable path problem. | Y**Y
发帖数: 66 | 4 D(S, 0) = 0
D(v, 0) = infinity when v != S
loop i=1...K
D(v, i) = min {D(u, i-1)+w(u,v)}, for all edge (u, v) in E.
return D(T, K).
complexity K*(|V|+|E|)
K
【在 b*******e 的大作中提到】
: A graph, find the shortest path between S and T with the number of edges = K
: .
: What is the complexity of your algorithm.
| b*******e
发帖数: 217 | 5 anyway, shortest path is a DP.
Spath(s, V) = Min(SPath(s, Parent of v) + W));
here introduce one more dimension: number k of edges.
【在 b*******e 的大作中提到】
: this is a DP problem.
: SPath(S, V, K) = Min(SPath(S, Parents of V, K-1) + W)
: this is called shortest reliable path problem.
| f*****e
发帖数: 2992 | 6 点边都可以重复，牛啊。
【在 b*******e 的大作中提到】
: this is a DP problem.
: SPath(S, V, K) = Min(SPath(S, Parents of V, K-1) + W)
: this is called shortest reliable path problem.
| b*******e
发帖数: 217 | 7 why? ANY THING WRONG WITH THE RECURSIVE FUNJCTION? i MAY MISS SOMETHIGN...
THOUGH.
"PARENT" INDICAES NOT GO BACK. |
|
