wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Vertecies Subset Shortest Path
        
(Message started by: Dudidu on Dec 14^th, 2003, 4:54am)

Title: Vertecies Subset Shortest Path
Post by Dudidu on Dec 14^th, 2003, 4:54am

Let G=(V,E) be an undirected graph, let W[subseteq]V and let s,t be two vertices (i.e. s,t [in] V).
Devise an efficient algorithm for finding a path from s to t that passes through a minimal number of vertices from W.

Title: Re: Vertecies Subset Shortest Path
Post by towr on Dec 16^th, 2003, 2:56am

I can't think of anything better than O(V²), and obviously that's not good enough..

Title: Re: Vertecies Subset Shortest Path
Post by Dudidu on Dec 16^th, 2003, 6:19am

on 12/16/03 at 02:56:02, towr wrote:

I can't think of anything better than O(V²), and obviously that's not good enough..

You are right, I'm looking for something better.
Hint 1:[hide] think how to reduce this problem to another problem...[/hide]

Title: Re: Vertecies Subset Shortest Path
Post by James Fingas on Dec 16^th, 2003, 6:38am

The generic solution is [hide]Djikstra's algorithm[/hide], which can solve this problem in O(E), but we can make a much simpler version specifically for this problem:

[hide]If W=V, then a breadth-first search will do the trick. We put the nodes into a queue when we find them, then pull them out the front to see where they go. But the nodes that are not in W do not count in the search, so we put them in a different queue and process them before carrying on with the nodes that are in W. We mark the nodes to remember where we've been.

queue qV, queue qW
array M = {0,0,0,0,...}
vertex i = s
edge e
loop until break {
for all e in i.edges do {
if e.destination in W then
if M[ e.destination ] = 0 then {
qW.pushback( e.destination )
M[ e.destination ] = 1
}
else
if M[ e.destination ] = 0 then {
qV.pushback( e.destination )
M[ e.destination ] = 1
}
}
if not qV.empty
i = qV.popfront
else
i = qW.popfront
if i = t then break
}[/hide]

It would take a bit of modification for this simple solution to store the route.

Title: Re: Vertecies Subset Shortest Path
Post by Dudidu on Dec 17^th, 2003, 10:41pm

on 12/16/03 at 06:38:35, James Fingas wrote:

The generic solution is [hide]Djikstra's algorithm[/hide], which can solve this problem in O(E)...

This is what I was looking for ! (but why Djikstra in this case takes O(n) (for those who do not know why) !?)

Quote:

[hide]If W=V, then a breadth-first search will do the trick...[/hide]

Obliviously...

Quote:

[hide]We put the nodes into a queue when we find them, then pull them out the front to see where they go....[/hide]

The general idea seems to be correct but I have a question - how would you implement the queue(s) so they will support insertion/decrease-key/extract-min in O(1) ?

Good work, James ;D!

Title: Re: Vertecies Subset Shortest Path
Post by James Fingas on Dec 18^th, 2003, 3:30am

If I was really perverse, I'd just make the "queues" rotating arrays the same size as W. That would do the job trivially.

Hmm ... it looks like you're under the mistaken assumption I'm using priority queues. They're just regular queues where you push on the back and pop from the front--the order of the elements never changes.

Title: Re: Vertecies Subset Shortest Path
Post by Dudidu on Dec 18^th, 2003, 4:36am

on 12/18/03 at 03:30:52, James Fingas wrote:

Hmm ... it looks like you're under the mistaken assumption...

You're right, I didn't pay enough attention :(.