1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oooh I got it! But what about reachability problems? Like transitive closures. $\endgroup$ – BrandNewStory Oct 28 at 15:52
  • $\begingroup$ @BrandNewStory Those usually take cycles into account, if edges are directed. $\endgroup$ – orlp Oct 28 at 18:35
  • $\begingroup$ Thank you so much!:) $\endgroup$ – BrandNewStory Oct 29 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.