Author |
Topic: Vertecies Subset Shortest Path (Read 1307 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Vertecies Subset Shortest Path
« on: Dec 14th, 2003, 4:54am » |
 Quote  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: 
Posts: 13730
|
|
Re: Vertecies Subset Shortest Path
« Reply #1 on: Dec 16th, 2003, 2:56am » |
Quote 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 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
Gender:
Posts: 949
|
|
Re: Vertecies Subset Shortest Path
« Reply #3 on: Dec 16th, 2003, 6:38am » |
Quote 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 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  !
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Vertecies Subset Shortest Path
« Reply #5 on: Dec 18th, 2003, 3:30am » |
Quote 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 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  .
|
| « Last Edit: Dec 18th, 2003, 4:36am by Dudidu » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print