Re: shortest path with constraints that some nodes can not be on the same pth
- From: "almeidaraf@xxxxxxxxx" <almeidaraf@xxxxxxxxx>
- Date: 17 Jun 2005 08:00:41 -0700
It's just an idea. Can't you just remove all the vertices that can't be
together and try to find the shortest path without them, then include
one and remove all the others, and then change the vertex that is
included. That would be O(n) so i think you wouldn't be turning your
algorithm in exponential one that way.
example
you have v1, v2, v3, v4, v5, v6
v2, v3 and v5 can't be together and you have to find the shortest path
from v1 to v6.
You remove from your graph v2, v3 and v5 and try to calculate the
shortest path, if there's one. Then you add v2 to your graph and
calculate it again, then you remove v2 and add v3 and calculate the
shortest path and then do the same thing with v5. Now you can compare
the paths and keep the one that's the smallest one.
You can find the shortest path with that dijkstra algorithm, you
probably know that already.
.
- Follow-Ups:
- References:
- shortest path with constraints that some nodes can not be on the same pth
- From: news.usc.edu
- shortest path with constraints that some nodes can not be on the same pth
- Prev by Date: Re: ZFC
- Next by Date: A little advice on strategy (no solutions. Sorry)
- Previous by thread: shortest path with constraints that some nodes can not be on the same pth
- Next by thread: Re: shortest path with constraints that some nodes can not be on the same pth
- Index(es):
Relevant Pages
|
