# Distance function such that we visit every “color region” once [closed]

Consider the following image:

Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right.

We must go through each color exactly once, and once we go outside a color, we can't go back to the same one.

Here is a example of what I think is a optimal path:

As per dikisjtra algorithm, we update the distance at once node if d[current] + weight(this_node, next_node) < d[next_node]. Usually these weights are given to us, but in this case, we must create a weight function such that given any two pixels (x1,y1),(x2,y2), our path follows something like what I have drawn in white.

You can assume all the colors are indeed different, even though they might look similar because of shades.

I am thinking of the following conditions to check in the weight condition:

going from old color -> same color -> maybe a weight of 5

going from old color -> new color -> a low weight of 1

What are the cases of the weights I can assign so dijikistra finds the path shown in white?

• What is a "Dijkstra path"? And just weighting colour repeats to 5 won't help: that just says "repeat a colour if it cuts four or more steps from the path", not "never repeat a colour". – David Richerby Mar 16 '19 at 10:31
• I have updated the question to hopefully answer all of this – BoogleDoogle Mar 16 '19 at 13:55
• This coloring is very confusing to me. Since each small square has a different color, can we just remove all references to color? Instead we just say one square, another square, a different square, a new square etc. Or use "cell" and "a cell at a different place". – John L. Mar 18 '19 at 5:05

Solution to your problem: assign a weight of 1 to each edge in the path, and a weight of $$\infty$$ (or some very large number) to each edge not in the path. (It suffices to choose a weight that is larger than the number of vertices in the graph.) You can easily verify that the shortest path only uses edges of weight 1 (any path that includes any other edge will have a total distance that is larger than that of the desired path).