2
$\begingroup$

I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with the constraint that it can only move down or to the right.

It looks like the standard way to solve this is with the top-down dynamic programming approach but I was wondering if a graph traversal algorithm could also work.

The problem with graph traversal algorithms is that you do not revisit nodes that you have already seen but many unique paths can visit the same node. So if you got rid of the constraint that you cannot revisit a node, would a graph traversal method work here? This is also a special case where you cannot get stuck in an infinite loop because the robot can only go down or right so it can never go back to a node it has already been to.

$\endgroup$
1
$\begingroup$

There could be many paths. For example, if the grid is $n \times n$ and all edges are present, then there are $\binom{2n}{n} = \Theta\left(\frac{2^n}{\sqrt{n}}\right)$ paths. You don't want to be going through all of them. Using dynamic programming, you can come up with the answer without going over all paths individually. In other words, dynamic programming is much more efficient than your suggested algorithm.

$\endgroup$
  • $\begingroup$ That makes sense. I suppose graph traversal is better suited for "does a path exist" types of problems $\endgroup$ – user1893354 Sep 24 '18 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.