Do weights of edges affect the shortest path in 2D grid undirected graph

algorithmsgraph theorymathematical modelingpath-connectedsearching

I'm struggling with the shortest path finding problem in a road network in my program:

Given a map, the roads are arranged as a 2D grid, and the roads intersect to form a series of nodes. There are some obstacles such as lakes that make some roads in the grid missing, so the shortest distance between any two points is not necessarily the Manhattan distance.

For any two points, we first find a shortest path; then, assuming that the passing time of the horizontal road between every adjacent node is different from that of the vertical, we find a road that takes the shortest time. Abstractly speaking, it is to assign the same weight to all horizontal edges in the undirected graph, and then assign another weight to all vertical edges, and then use the algorithm to find the shortest path.

Does the set of shortest paths in the two cases coincide? Or, calculate the total passing time of the shortest path in the first case after weighting, is this time equal to the total passing time directly obtained in the second case?

My intuition tells me that it may be equal, and the output of the program seems to verify this. But I want to look for a rigorous proof process. This obviously holds true for cases where we don't need to get around obstacles, but it's not clear to me how to think of other cases. Thank you all!

Best Answer

Yes they effect the shortest paths! Imagine you have the following grid.

  1. You are at $(0,0)$
  2. Want to get to $(1,1)$
  3. The edges that exist are $(0,0)-(1,0)$, $(1,0)-(2,0)$, $(2,0)-(2,1)$, $(2,1)-(1,1)$, $(1,1)-(1,2)$, $(1,2)-(0,2)$, $(0,2)-(0,1)$, $(0,1)-(0,0)$.

So your two options are

  1. Go to the right 2, then up 1, the left 1 - so 3 horizontal and 1 vertical.
  2. Go up 2, then right 1, then down 1 - so 1 horizontal and 3 vertical.

If the horizontal and vertical weights are the same, then both these paths have the same distance. If the horizontal and vertical weights differ then the shortest (whether it is 1 or 2) depends on weights!

Related Question