Today’s Leetcode July Challenge is an interesting generalized graph problem that I’d like to look at a couple of approaches and optimizations for. We’re given a directed acyclic graph as an adjacency list, with nodes are labeled by their 0-based index in the list, and asked to return a list containing all valid, ordered paths from the first to last node–node index 0 to node index adjacency list length - 1. This immediately strikes me as an NP-complete problem, as finding a polynomial time solution to this problem would generalize to all NP problems, thinking specifically of the entire category of path problems, meaning that we can expect an exponential best case asymptotic runtime algorithm. Thankfully we’re given a problem constraint that the number of nodes will be in the range [2,15], making our computations feasible. With a high complexity problem such as this, I like to look at a few different ways to write the algorithm with some early optimizations, but first let’s look at the simple example graph.

Input: [[1,2,3],[2,3],[3],[]]
graph LR; 0((0))-->1((1)) 0((0))-->2((2)) 0((0))-->3((3)) 1((1))-->2((2)) 1((1))-->3((3)) 2((2))-->3((3)) 
Output: [[0,3],[0,1,3],[0,2,3],[0,1,2,3]]

Cool, so let’s work on an algorithm. If you’ve read many of my other posts, you know that I typically think of recursion as a useful tool for understanding and prototyping an algorithm, but ultimately prefer iterative solutions. We’ll follow the same path on this problem, but I will say that the recursive backtracking solution I implement is especially suited to efficiently solving this problem. You’ll see that the algorithm uses tail recursion to build the paths. The longest possible path in a directed acyclic graph will be a Hamiltonian path that visits every node, which means that the maximum recursion depth will be equal to the number of nodes in the graph–extremely feasible for our constraints. All of the backtracking algorithms work by progressively building building a list starting from the root node until it reaches the target node or is exhausted, at which point the path is backtracked to the previous node and alternate paths are tried.

Here’s a look at my initial algorithm:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
   if(graph.empty()) return {{}};
   
   vector<vector<int>> paths;
   vector<int> path;
   
   dfs(graph, paths, path, 0, graph.size()-1);
   return paths;
}
void dfs(vector<vector<int>>& graph, vector<vector<int>>& paths, vector<int> path, int currentNode, int targetNode) {
   path.push_back(currentNode);

   if(currentNode == targetNode) {
	  paths.push_back(path);
	  return;
   }
   for(auto adjacentNode : graph[currentNode]) {
	  dfs(graph, paths, path, adjacentNode, targetNode);
   }
}

This implementation works pretty well, but I wanted to make some optimizations to both improve the algorithm as well as make it easier to translate to an iterative approach. Note: the following implementation actually performed the best of all my implementations on the problem’s test case suite.

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
   if(graph.empty()) return {{}};
   
   vector<vector<int>> paths;
   vector<int> path = {0};
   
   dfs(graph, paths, path, 0);
   return paths;
}
void dfs(vector<vector<int>>& graph, vector<vector<int>>& paths, vector<int>& path, int currentNode) {
   // no need to pass targetNode value on the stack as it's always the number of nodes - 1.
   if(currentNode == graph.size()-1) {
	  paths.push_back(path);
	  return;
   }
   for(auto adjacentNode : graph[currentNode]) {
	  // optimize by passing current path by reference and manually backtrack by popping back node.
	  path.push_back(adjacentNode);
	  dfs(graph, paths, path, adjacentNode);
	  path.pop_back();
   }
}

From that algorithm, it’s an easy jump to an iterative algorithm. Because the previous, recursive algorithm performed so well, I would describe my current iterative implementation as functional but incomplete–there’s still a lot of inefficiency in the path building and is memory intensive. It’s still worth looking at as the basis for a better, non-recursive implementation. I’ve also included a breadth-first algorithm as an extra, but it’s not really optimal for this problem as it isn’t backtracking and will result in concurrently storing a larger number of paths in memory.

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
   if(graph.empty()) return {{}};
   
   vector<vector<int>> paths;
   
   int targetNode = graph.size()-1;
   stack<pair<int,vector<int>>> s;
   s.push({0, vector<int>(1)});
   while(!s.empty()) {
	  const auto [currentNode, path] = s.top();
	  s.pop();
	  
	  if(currentNode == targetNode) {
		 paths.push_back(path);
	  }
	  for(const auto adjacentNode : graph[currentNode]) {
		 vector<int> branch(path);
		 branch.push_back(adjacentNode);
		 s.push({adjacentNode, branch});
	  }
   }
   return paths;
}

Breadth-first search:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
   if(graph.empty()) return {{}};
   
   vector<vector<int>> paths;
   
   int targetNode = graph.size()-1;
   queue<pair<int,vector<int>>> q;
   q.push({0, vector<int>(1)});
   while(!q.empty()) {
	  const auto [currentNode, path] = q.front();
	  q.pop();
	  
	  if(currentNode == targetNode) {
		 paths.push_back(path);
	  }
	  for(const auto adjacentNode : graph[currentNode]) {
		 vector<int> branch(path);
		 branch.push_back(adjacentNode);
		 q.push({adjacentNode, branch});
	  }
   }
   return paths;
}