# Lower bound for shortest problem

Suppose given a weighted directed graph $$G=(V,E)$$. We want, for each $$v\in V$$ find a path $$P$$ from other vertices to $$v$$ such that weight of $$P$$ is minimzed.

I can solve this by running Johnson's algorithm on $$G$$ and doing a linear traverse of matrix to find out for each $$v$$ minimum weight shortest path from other to $$v$$ in $$O(n^3)$$. But my problem is are there any lower bound that show us we can't do better in $$\Omega(n^3)$$?

If you want a simple path: You cannot solve this in $$O(n^3)$$ time (unless $$P=NP$$).
• Now can we conclude that, we can solve it in $O(n^3)$ or not? Nov 16 '21 at 13:31