Advertisement
kai-rocket

All Paths from Source to Target

Mar 26th, 2021 (edited)
677
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.02 KB | None | 0 0
  1. class Solution:
  2.     def get_all_paths_from_src(self, graph, src_node):
  3.         # Initialise list of paths to return from src_node to tgt_node
  4.         final_paths = []
  5.         # Retrieve list of adjacent nodes
  6.         adj_nodes = graph[src_node]
  7.         # For each adjacent node an leading out of source node sn
  8.         for adj_node in adj_nodes:
  9.             if adj_node == len(graph) - 1:
  10.                 final_paths.append([src_node, adj_node])
  11.             else:
  12.                 # Generate all paths to end node en from an (recursive), return list of paths
  13.                 downstream_paths = self.get_all_paths_from_src(graph, adj_node)
  14.                 # Add those paths to my final list of paths
  15.                 for downstream_path in downstream_paths:
  16.                     final_paths.append([src_node] + downstream_path)
  17.         # Return my final list of paths
  18.         return final_paths
  19.    
  20.     def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
  21.         return self.get_all_paths_from_src(graph, 0)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement