I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't understandThe basic idea is :DFS-Visit(s)Change current status to currently visitingIf neighbor is t -> print the path (from the stack trace or any way)If not: DFS-Visit on neighborsWhen done visiting neighbors: change status to not-visited yetIt seems like it's run-time is exponential, however - could I use the memorization technique like in dynamic programming to turn this into linear time ? since a lot of calculations are repeatingThe example given in the algorithm is a DAG, but I couldn't find an regular graph that makes this algorithm fail.It seems highly unlikely that this algorithm is possible in linear time on a regular graph... Wouldn't that help me to calculate shortest path from s to t in linear time ?
Finding all paths from s to t in linear time
algorithms;graphs;enumeration