Suppose the graph has n colors. Think of all vertices with same color
as lying in a same cluster. Hence all we need is the shortest path
that goes through some vertex in each of the n clusters.
After the ith step suppose we have all the shortest paths, starting
from each vertex in the ith cluster, that goes through all the
remaining clusters. In the (i+1)th step, we add a new cluster. Try to
find out the shortest path that starts from each vertex Vj lying in
this new cluster such that:
Shortest path starting from Vj = min{ dist(Vj, Vi) + Shortest path
starting from Vi}; where Vi is any vertex belonging to the ith
cluster.
At the end of nth step, take the minimum of all shortest paths
starting from the nth cluster.
Regards,
Satish
On Feb 25, 6:47 pm, Ridvan <[EMAIL PROTECTED]> wrote:
> Maybe this will work:
> Starting from each vertex using BFS calculate the shortest path which
> passes through vertexes from all the colors.
>
> Best,
> Ridvan
>
> On Feb 24, 2:00 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote:
>
>
>
> > On 2/24/08, Sticker <[EMAIL PROTECTED]> wrote:
>
> > > I have a graph problem, which is different from the standard salesman
> > > problem. I say it is more difficult.
>
> > > In a graph, I have many vertexes with different colors. It is more
> > > easier to think of each vertex as a shop selling only one goods and
> > > vertexes with the same color selling the same goods. There are edges
> > > between any two vertexes, with different distances.
>
> > > You start at a specific position (different from any vertex), and have
> > > a list of goods you need to buy. Figure out an optimal path with
> > > shortest distance so you can get all the goods from the shops on the
> > > path. You are not required to start and end at the same position and
> > > edges and vertexes can be visited more than once if you want.
>
> > > If there is no color on vertex, or in other words, each vertex sells a
> > > distinct goods, then the above problem is identical to salesman
> > > problem.
>
> > I dont think that makes is identical to TSP. Cause in TSP you have to visit
> > every node.
> > But in this case you are given a list of goods and each vetex sells unique
> > good.
> > Also in TSP we have to return to the start point , but this is not the case
> > here !
>
> > But now we have colors on vertexes and once a vertex with a
>
> > > color is visited, you don't want to visit vertex with the same color
> > > (which will only increase the total distance).
>
> > > Since this problem is an extension of the standard salesman problem,
> > > the practical solution is probably heuristic. The key is, what
> > > heuristic strategy are you going to use.
>
> > > I think the problem a bit and come up with a very naive solution:
>
> > > For each vertex, calculate its distances to the closest vertexes with
> > > other colors. For vertexes with the same color, choose the one with
> > > the minimum total/average such distances. Then, only one vertex with a
> > > color is remained in the graph. Then use heuristic strategy for
> > > salesman problem.
>
> > > any other idea?
>
> > --
> > Ciao,
> > Ajinkya- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
