Re: shortest path with constraints that some nodes can not be on the same pth
- From: "news.usc.edu" <ganglu@xxxxxxx>
- Date: Wed, 22 Jun 2005 13:15:23 -0700
But there could be many such constraints. Actually every node is constrained
with some other nodes. So there would be no nodes left.
<almeidaraf@xxxxxxxxx> wrote in message
news:1119020440.943294.276130@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> 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.
>
.
- References:
- shortest path with constraints that some nodes can not be on the same pth
- From: news.usc.edu
- Re: shortest path with constraints that some nodes can not be on the same pth
- From: almeidaraf@xxxxxxxxx
- shortest path with constraints that some nodes can not be on the same pth
- Prev by Date: fsa: compleixity and frequency
- Next by Date: Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
- Previous by thread: Re: 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
|
