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
What makes you think that this is a DFS? In your last post I told you that it is called dynamic programming, not DFS.
Hmm, Top-down DP comes from recursion. You can remove the memo, and it would be DFS, right ?.
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.
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.
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.
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:
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.
Which software/tool did you use to draw that graph?
I've googled "online graph nodes edges" (last two words to distinguish it from plots), got this StackOverflow answer and this tool