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?