wu :: forums
« wu :: forums - Vertecies Subset Shortest Path »

Welcome, Guest. Please Login or Register.
Dec 24th, 2024, 8:00am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Icarus, towr, william wu, SMQ, ThudnBlunder, Grimbal, Eigenray)
   Vertecies Subset Shortest Path
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Vertecies Subset Shortest Path  (Read 1322 times)
Dudidu
Full Member
***





   


Posts: 227
Vertecies Subset Shortest Path  
« on: Dec 14th, 2003, 4:54am »
Quote Quote Modify Modify

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Vertecies Subset Shortest Path  
« Reply #1 on: Dec 16th, 2003, 2:56am »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member
***





   


Posts: 227
Re: Vertecies Subset Shortest Path  
« Reply #2 on: Dec 16th, 2003, 6:19am »
Quote Quote Modify Modify

on Dec 16th, 2003, 2:56am, towr wrote:
I can't think of anything better than O(V2), and obviously that's not good enough..
You are right, I'm looking for something better.
Hint 1: think how to reduce this problem to another problem...  
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Vertecies Subset Shortest Path  
« Reply #3 on: Dec 16th, 2003, 6:38am »
Quote Quote Modify Modify

The generic solution is Djikstra's algorithm, which can solve this problem in O(E), but we can make a much simpler version specifically for this problem:
 
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
}

 
It would take a bit of modification for this simple solution to store the route.
« Last Edit: Dec 16th, 2003, 6:52am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
Dudidu
Full Member
***





   


Posts: 227
Re: Vertecies Subset Shortest Path  
« Reply #4 on: Dec 17th, 2003, 10:41pm »
Quote Quote Modify Modify

on Dec 16th, 2003, 6:38am, James Fingas wrote:
The generic solution is Djikstra's algorithm, 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:
If W=V, then a breadth-first search will do the trick...
Obliviously...
Quote:
We put the nodes into a queue when we find them, then pull them out the front to see where they go....
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  Grin!
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Vertecies Subset Shortest Path  
« Reply #5 on: Dec 18th, 2003, 3:30am »
Quote Quote Modify Modify

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.
« Last Edit: Dec 18th, 2003, 3:32am by James Fingas » IP Logged

Doc, I'm addicted to advice! What should I do?
Dudidu
Full Member
***





   


Posts: 227
Re: Vertecies Subset Shortest Path  
« Reply #6 on: Dec 18th, 2003, 4:36am »
Quote Quote Modify Modify

on Dec 18th, 2003, 3:30am, James Fingas wrote:
Hmm ... it looks like you're under the mistaken assumption...
You're right, I didn't pay enough attention Sad.
« Last Edit: Dec 18th, 2003, 4:36am by Dudidu » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board