jaswanthi's blog

Why DFS can't be used for shortest distance on graph, but works on tree
By jaswanthi, 9 years ago, In English

EDIT For followup Question:

Thanks for the clarifications :)

But, One follow-up question is that, In this problem https://oj.leetcode.com/problems/triangle/, you can reach a node in different ways, but it can be solvable with DFS.

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;
    }   
}

=====================================================================

Original post:

Why we cannot use DFS to find the shortest distance on the graph/mazes, while it can be used on the tree.

How can I formally prove that even a modified DFS doesn't work.

For ex: we can solve this one ( https://oj.leetcode.com/problems/triangle/) easily with DFS.

Thanks for your help !!!

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

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

Because in a tree you can reach a node in unique way.

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

Because in the tree there is only one path from one verticle to another. DFS is taking one way and going by that way (there's no gurantee that way is the best), but in tree there is as that way is unique.

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

    But, I can enumerate all the paths of the graph with DFS, and select the shortest one, right ?

    def DFS(graph,start,end,path=[],shortest=None):
	path=path+[start]
	if start == end
	 	return path

	for node in graph.childrenOf(start):
		if node not in path # Avoid cycles
			if shortest=None or len(path) < len(shortest):
				newPath = DFS(graph,node,end,path,shortest)
				if newPath != None:
					shortest = newPath
	return shortest
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sometimes there is an exponential number of such paths. For example:

      X X X X X X X X X X
|\|\|\|\|\|\|\|\|\|\
Y-X-X-X-X-X-X-X-X-X-Z

      There are 1024 paths from Y to Z (and if there are n layers, we have 2n paths). And note there is only one shortest path.

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

      edit: misunderstood the question :)

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why down vote ?

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

Thanks for the clarifications :)

But, One follow-up question is that, In this problem https://oj.leetcode.com/problems/triangle/, you can reach a node in different ways, but it can be still solvable with DFS.

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

    Can you explain how to solve it with DFS, please? I think that this is a simple DP problem.

    → Reply