I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(including circles) in the result. Is it because the complexity is way too expensive? Thanks in advance for your help!
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
3
When solving most optimization problems on paths (e. g. shortest, longest path) a cycle is either useless or makes the optimum not exist (allowing infinitely long or short paths). Thus there's generally no point in allowing cycles.
-
$\begingroup$ Oooh I got it! But what about reachability problems? Like transitive closures. $\endgroup$ – BrandNewStory Oct 28 '20 at 15:52
-
$\begingroup$ @BrandNewStory Those usually take cycles into account, if edges are directed. $\endgroup$ – orlp Oct 28 '20 at 18:35
-
