jaswanthi's blog

Why shortest path with DFS works in this Graph ?
By jaswanthi, 10 years ago, In English

The general understanding is that we can't use DFS in graph for finding shortest path.

But, I am having difficult time understanding why the DFS works for following problem, even though a node can be reached in multiple ways. https://oj.leetcode.com/problems/triangle/

Also,What kind of shortest path problems can be solved with DFS ?

I understand that we can use Uniform Cost search ( similar one Dijkstra) for finding shortest path.

Solution with DFS for above problem: 

public class Solution {
    int[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new int[triangle.size()][triangle.size()];
        for(int i = 0; i < triangle.size(); i++) {
            Arrays.fill(memo[i], Integer.MIN_VALUE);
        }
        return minimumTotal(triangle,0,0);
    }
    public int minimumTotal(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size() -1)
           return triangle.get(i).get(j); // base case
        //if(memo[i][j] != INTEGER.MIN_VALUE) {
        //    return memo[i][j];
        //}
        int sum0 = minimumTotal(triangle, i+1, j);
        int sum1 = minimumTotal(triangle, i+1, j+1);
        int res = Math.min(sum0, sum1) + triangle.get(i).get(j);
        memo[i][j] = res;
        return res;
    }   
}

PS: If you think the problem doesn't have a goal state, We can modify the problem to have a goal state, For ex. To reach some indexed position from the top row.

And, We could still use DFS for it.

My Question is more towards following, How to define the boundary for shortesr path priblems solvable on graph using DFS

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What makes you think that this is a DFS? In your last post I told you that it is called dynamic programming, not DFS.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Hmm, Top-down DP comes from recursion. You can remove the memo, and it would be DFS, right ?.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've heard an idea from Burunduk1, that (almost?) every DP is a DFS on a specific graph of states, and I agree with that.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        It depends on how do you define 'DFS' and 'DP'

        I prefer to distinguish DFS and recursive DP/bruteforce. Nevertheless, they are very and very similar in terms of implementation, that's true.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'd call it 'bruteforce', not DFS. DFS, ihmo, is something graph-related: it either traverses the graph and prints some ordering of vertices or find any particular path to the goal (not necessarily the shortest one). I'd say that the last property ('greediness' of DFS) is the one that makes difference between DFS and recursive brute-force. In DFS, when you find a path, you exit immediately. In bruteforce you try all of the paths and choose the best one.

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

No matter how do we call this approach (I'd stick with 'recursive DP with memoization' or 'bruteforce with memoization') there is one thing that matters: graph is acyclic.

This implies that previous states of DP does not matter for calculation of the current state, because there is no way to go back. So, we can have the 'after function returns its value is absolutely correct and it returns in a finite time' invariant.

We can have some problems, depending on implementation:

  1. Infinite loop, if we update memoization array once in the end of function. That way your function will call itself indirectly and you guess what happens next. And I didn't even mention negative cycles. Oops, I just did.
  2. Incorrect result, if you perform all calculations in memoization array without intermediate variables. I.e. you keep current result in the array even if your function haven't completed its calculations yet. Imagine the following indirected weighted graph:

We start from vertex A and then go in order A → C → B → D. Our goal is D, answer for D is obviously zero (I consider 'answer' here as 'minimal distance to the goal'). Then we return to B and try to calculate answer for it. We have no calculated answer for C and we don't go there because this vertex is already in the stack. Thus, we go to D directly and calculate answer for B as 10+0=10, which is already incorrect, but may be that won't affect us? Unfortunately, it will. We return to C and correctly calculate answer as 1, because there is such direct edge to D. But we do not recalculate answer for B — we assume that is's already correct as corresponding function ended its execution already. At last, we return to A and select the best among two choices: go through C for 10+1=11 or go through B for 1+10=11. Anyway, answer is 11 instead of correct 3.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which software/tool did you use to draw that graph?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've googled "online graph nodes edges" (last two words to distinguish it from plots), got this StackOverflow answer and this tool

      → Reply