Dijkstra's algorithm is known to solve shortest path problems in $O(|V|^2)$ where $V$ is the set of vertices and $E$ is set of edges.
However I just finished studying minimum cost network flow problems, implemented a few solutions for shortest path calculations, that can be solved as LPs, which always finds the optimal solution. If we think of the code behind the scenes, LPs can be numerically solved through log-barrier approach and the Newton's method. Then, since Newton steps never exceed 10-15 steps, and in each the biggest cost is calculating the Jacobian matrix, which in case of a network problem is banded, structured, so it can be inverted in $O(|E|)$, meaning faster than Dijkstra performance. $|V|^2$ means potentially checking all pairs of nodes, but networks are sparse, each node is not connected to each other node, $O(|E|)$ only pays a price proportional to edges that exist.
Would this be a correct assessment?
Best Answer
Maybe take a look at this paper https://arxiv.org/abs/2003.08929