The problem statement is We are given a 2D grid with multiple source cells. For every cell (x,y), we need to compute the minimum cost to any source, where the cost between two cells is defined as the squared Euclidean distance: cost((x,y),(u,v))=(x−u)^2 + (y−v)^2 I am interested in the reason why dijkstra would fail such task if I start propagation from source nodes, keeping the best_source[x][y] for each visited cell. I understand that the issue is related to the non-linearity of the cost function, but I don’t have a strong intuition for why exactly Dijkstra fails here. What are good ideas or models to easily get why it fails? also, any instances of this problem would be appreciated.
Dijkstra should work, assuming you include an edge between every pair of points on the plane. Dijkstra works on general graphs, and this is just one specific example of a type of graph. The problem here is that it's slow, because you have an edge between any pair of points.
Nevertheless, the problem seems quite difficult and probably requires advanced technique. Maybe you've made an incorrect or unnecessary reduction; can you send a link to the statement?
By the way, a notable case to consider occurs with obtuse triangles, which satisfy a^2 + b^2 < c^2; in this case you want to traverse the two shorter edges instead of the one longer edge, which is interesting to examine.