blueslime's blog

Help: Weird Graph Problem
By blueslime, 15 months ago, In English

Given an n x m integer matrix, find the shortest path from (0,0) to (n-1,m-1) such that the sum of values along the path is minimum, and the path is also lexicographically smallest among all the paths with minimum sum. You are allowed to move up, down, left, right. Print the path as a string of letters L (left), R (right), U (up), D (down).

1 <= n <= 1000, 1 <= m <= 1000

I presume this is a modification of Dijkstra but I do not know how to do it. Can anyone help?

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
15 months ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

Well, without needing to output the path, this is a direct Djikstra. You can also run a Djikstra on a modified cost function (sum of values, path) to find the path (i.e., your starting cost is (0, ""), and if you e.g. go right, your cost becomes (num[0][1], "R")), but that adds $$$O(N)$$$ to the complexity because of string comparisons.

To solve this faster, run a cost-only Djikstra in reverse — start in $$$(n-1, m-1)$$$ and find the path to $$$(0, 0)$$$. Whenever you can reach a given node with a shortest path in multiple ways, choose the one (i.e., record the "previous"/"parent") that comes from the lexicographically first direction (i.e., D < L < R < U). Should be provable by induction that this generates the lexicographically smallest path.

→ Reply
  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I don't think that this would work, take a look at this example: 

    1 1 1
1 9 1
1 1 1

    Obviously the minimum cost is 5 and the competing paths are RRDDand DDRR. Starting from the end, you would pick the path coming from up, as D < R, which is incorrect as it gives RRDDas the answer.

    → Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Well, what essentially Dijkstra is doing, it's building a directed tree from the source node to all the reachable nodes. At each iteration, a new leaf is added to the tree (the one currently processed vertex). It never modifies the already build tree.

So what you can do is essentially a dynamical LCA on this tree. Each time you add a vertex, remember its 1-st, 2-nd, 4-th, 8-th... parent pointers. Then, to compare from which direction to come from in the case of equal sums, find the LCA of the competing nodes and look how the paths diverged. Then pick the one which diverged in lexicographically smaller direction. This makes the entire solution $$$O(nm \log(nm))$$$.

→ Reply