Timeline for Finding all paths on undirected graph
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2021 at 18:09 | history | edited | rgrig | CC BY-SA 4.0 |
edited body
|
| Jun 8, 2021 at 17:32 | comment | added | Everyone |
@rgrig i believe it should be if y not in path: instead of if y not in seen: in the search function.
|
|
| May 24, 2021 at 6:17 | comment | added | rgrig | @Everyone, Thanks! I think I fixed these problems now. | |
| May 24, 2021 at 6:15 | history | edited | rgrig | CC BY-SA 4.0 |
added 33 characters in body
|
| May 23, 2021 at 5:13 | comment | added | Everyone |
I realize this is coming 10 years later, but there are two major flows in the algorithm: 1. it doesn't stop going after reaching the destination. Could be fixed by return after print path. and 2. there is nothing to prevent circular endless loop between two nodes on one edge. Can be fixed by checking if the next node is already on the stack. This will require more changes to the way things are pushed and popped into the stack.
|
|
| Mar 19, 2014 at 15:56 | comment | added | CppLearner |
What exactly is t??
|
|
| Aug 2, 2013 at 14:53 | comment | added | hhh | I cannot understand the condition in which this algorithm stops. This sequence determines the amount of paths here but how does the algorithm actually select which path to consider and which not? Just cut out paths above certain length? | |
| Jul 28, 2013 at 10:24 | comment | added | hhh | Can you elaborate on $O((np+1)(m+n))$? How did you come up with it? | |
| Apr 19, 2012 at 22:55 | comment | added | Brendan McKay | This method is correct. Maybe you can reduce the running time per path if you don't do the stuck() test so often. Maybe something like calling stuck() if a path to the destination hasn't appeared in the past $n$ steps can be made to work? The details would be a little hairy. | |
| Mar 19, 2010 at 19:21 | history | undeleted | rgrig | ||
| Mar 19, 2010 at 19:21 | history | edited | rgrig | CC BY-SA 2.5 |
fixed asymptotics (graphs could be disconnected)
|
| Mar 18, 2010 at 18:33 | history | deleted | rgrig | ||
| Mar 18, 2010 at 18:31 | history | answered | rgrig | CC BY-SA 2.5 |