Distance function such that we visit every "color region" once 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) &lt; 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?
Summary of your problem: You have a graph and a particular path through the graph, and you want to assign weights to the edges so that running Dijkstra's algorithm on that graph will give you that path.

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).