I'm trying to devise a $O(|V| + |E|)$ algorithm to calculate number of shortest paths between $s$ and $f$ on a undirected, unweighted graph. Can someone please check my pseudo-code? Also, isn't

$O(|V| + |E|) + O(|V| + |E|)$ = $O(|V| + |E|)$? enter image description here

  • 1
    $\begingroup$ We typically don't check answers. We can help you if you have any specific doubts. $\endgroup$ Commented Oct 12, 2021 at 17:10
  • $\begingroup$ @YuvalFilmus I'm trying to self learn and I didn't find this coding problem online so I'm unable to verify if my solution is fine. For recursive solutions, I struggle to show their correctness $\endgroup$
    – chesslad
    Commented Oct 12, 2021 at 17:22
  • $\begingroup$ This is not a coding problem, but rather its an algorithmic problem. The best way to verify your answer is to try to prove it (mathematically). The proof should be similar to that of BFS. $\endgroup$
    – nir shahar
    Commented Oct 12, 2021 at 18:25
  • $\begingroup$ A $O(|V|+|E|)$ algorithm doesn't mean much. The big-oh notation denotes a set of functions. You probably meant A an algorithm with time complexity of $O(|V|+|E|)$. $\endgroup$
    – Steven
    Commented Oct 12, 2021 at 18:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.