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 understand
The basic idea is :
- Change current status to "currently visiting"
- If neighbor is t -> print the path (from the stack trace or any way)
- If not: DFS-Visit on neighbors
- When done visiting neighbors: change status to "not-visited yet"
It 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 repeating
The 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 ?