Q1: given 2 nodes in a graph containing N (eg 121) nodes, potentially with cycles, generate all simple paths between the pair. A simple path has no cycle. (In other words, length + 1 == # unique nodes in a simple path)
- I think there are classic math algorithms for it, because this is part of basic graph theory. Here are some applications of this type of algorithms —
- Q1b (special case of Q1): given 2 nodes in a C by R matrix grid, where every node is connected to (up to) four neighbors, generate all cycle-free paths.
- I can solve this problem in python
- Q2 (easy one based on Q1): generate
all simple paths between any node pairin a graph. The shortest simple path has length=0. Longest simple path can potentially visit every node exactly once.
- A: first generate all 121-Choose-2 node pairs. For each pair, solve Q1. Lastly generate the 121 trivial paths of length=0.
- Q2b (special case of Q2): given a C by R (eg 11×11) matrix grid, where every node is connected to (up to) four neighbors, generate all simple paths.
- Q2c (easy one based on Q2): given a binary tree containing no cycles, generate all paths.
— my DFT implementation (probably not 100% correct) , where each “trail” either fails or becomes a path.
- from NodeA start a breadcrumb/trail. We can’t revisit any node already visited on current breadcrumb,
- if this is a matrix, then instead of a hashtable, we can also use a shadow matrix, but the breadcrumb is much smaller than a shadow matrix
- if we can reach a node surrounded by nodes on the same breadcrumb, then the trail fails
- else we will reach NodeB 🙂 Print the breadcrumb
By construction, we won’t see duplicate paths 🙂
https://github.com/tiger40490/repo1/blob/py1/py/grid/classic_count4waySimplePaths.py is the implemnetation
–BFT? I don’t think it can print each unique path