Consider the following image:

enter image description here

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:

enter image description here

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?

  • 1
    $\begingroup$ 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". $\endgroup$ – David Richerby Mar 16 '19 at 10:31
  • $\begingroup$ I have updated the question to hopefully answer all of this $\endgroup$ – BoogleDoogle Mar 16 '19 at 13:55
  • $\begingroup$ 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". $\endgroup$ – John L. Mar 18 '19 at 5:05

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

  • $\begingroup$ How can I do this progamactically though? In other words, what edges are the ones that give us that path^ ? We can assume the image is 100x100, giving 20x20 for each image $\endgroup$ – BoogleDoogle Mar 17 '19 at 15:31
  • $\begingroup$ @Tetra1, I assume you are given the path. The normal way to specify a path is as a list of sequence of vertices; from which each pair of adjacent vertices is an edge. $\endgroup$ – D.W. Mar 17 '19 at 15:50
  • $\begingroup$ Not given a path, the point is that we have to create that path using the weight function $\endgroup$ – BoogleDoogle Mar 17 '19 at 17:10
  • 1
    $\begingroup$ @Tetra1, sorry, I guess I don't understand your problem, then. Could you edit the question to make it clearer what the requirements for the algorithm are? What are the inputs? What are the outputs? What can we assume about the inputs to the algorithm? What conditions must the output satisfy, for the algorithm to count as satisfactory? $\endgroup$ – D.W. Mar 17 '19 at 17:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.