CODEWITHSUNDEEP
algorithmshortest-path
elias rizik
elias rizik

Reputation: 263

How to find the shortest colored path?

Given G=(V,E) Which is every edge has one of these three colors {green,red,blue}. We call a path "Colored Path" if he has all the three colors in it.

    Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s .
    output: algorithm that finds for every vertices v, a shortest path from s 
           that is Colored path

My solution is to walk through the graph, and count for every vertex the number of colors that the path has. Create 3 copies of the graph named G1,G2,G3

For every v that c(v) = 2 (c is number of colors from s to this path) connect v1 to v2 in the second graph(G2) with edge weight = 0.

for every edge c(v)= 3 connect from v2 (From G2) to v3 (To G3) with edge weight = 0 .

run dijkstra from s to t3 (in G3).

Is my solution Right ?

Upvotes: 2

Views: 2417

Answers (1)

MSalters
MSalters

Reputation: 180010

Doesn't look correct to me.

The easiest way is to realize that in normal Dijkstra, there's only one important thing to store in each node, and that's the absolute shortest path length from the root.

With colored paths, you have to store the shortest path length for every color combination. So, for 3 colors, you have to store the shortest red path, the shortest blue path, the shortest green path, as well as the shortest red-blue, red-green and blue-green paths, and finally the shortest red-green-blue path. (Total of 7 color combinations).

Upvotes: 1

Related Questions