0
$\begingroup$

I'm trying to practice some theory on graphs:

Namely, we have given connected undirected weighted graph with $N$ nodes and $M$ edges, let's say we want to find the shortest paths between node $1$ and node $N$. But, not only that we want to find all the paths with same shortest distance between $1$ and $N$.

Now I was wondering that if we have given $N = 300$ this number (of shortests paths) can be huge, my question is: is it possible to find all shortest paths in graph with at most 300 nodes in polynomial time.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If you limit the problem to $n \leq 300$, it can be solved in $O(1)$. If you don't limit $n$, there can be super-exponentially many shortest paths, so no. $\endgroup$
    – Raphael
    Commented Sep 3, 2017 at 21:50
  • $\begingroup$ I want to solve only for $n \leq 300$, what is the algorithm for getting O(1) ? $\endgroup$
    – someone12321
    Commented Sep 4, 2017 at 7:15
  • $\begingroup$ Every algorithm is in O(1) for fixed n -- asymptotics are meaningless in such a scenario. For real-world performance, the complexity theory perspective is utterly useless. You need to analyze algorithms in more detail, probably also incorporating the particulars of your set of possible inputs (can the general worst cases happen? are they likely?). To be frank, if you didn't understand my earlier comment this is probably beyond you. Just try out different algorithms and see which work best for you. $\endgroup$
    – Raphael
    Commented Sep 4, 2017 at 7:22

0

Reset to default