I will explain with an example:
3
a ------- b
| |
| |
| 5 | 4
| |
c---------d
1
lets say we want to find the shortest path from c to b,
denote sp(x,y) as the length of the shortest path from x to y
SP(c,b) = min( SP(c,a) + SP(a,b) , SP(c,d) + SP(d,b) ) // this step
should be done for all vertices other that the source and the sink.
which in this case is a and d.
this is fine but we must make sure that the resulting path is simple.
If the shortest path is P1(source,x) + P2(x,sink), assuming that the
recursive calls produce simple paths,
the shortest path from source to sink is also simple.
this is true since if the two paths returned share an vertex (other
than the end point) (say v), then P1(source,v)+P2(v,sink) is a shorter
path, violating the assumption of shortest path.
( this argument is valid iff the cycle corresponding to P1(v,x)
+P2(x,v) has non negative weight - else there is no notion of
"shortest path").
on the other hand, for longest path problem, such greedy choices wont
work.
For example consider the same recurrence this time but instead of
minimum find the maximum.
For the graph above,
LP(c,d) = 12 and the corresponding path is c-a-b-d
LP(d,b) = 9 and the corresponding path is d-c-a-b
both paths are simple but their concatenation results in a non simple
path.
(This is due to the nature of "longest". Think about it - its
definitely a bad guy...deserves its position in NP class...)
Hope you understood...
On Jun 28, 11:45 am, ankit sambyal <[email protected]> wrote:
> Shortest simple path problem is in P, but Longest simple path problem
> is in NP. Explain why the greedy choice(on edge weights) is not
> suitable in the second case .
>
> Ankit Sambyal
> BITS Pilani
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
