Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$? I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.
For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with a time complexity of $O(V+E)$. But above that, for an undirected graph with natural-number weights, it gives the best algorithm as an $O(E)$ algorithm due to Thorup (1999). This seems faster than the $O(V+E)$ for breadth-first search despite applying to a more general problem.
Am I correct in understanding that the $O(V+E)$ breadth-first search algorithm applies to a directed unweighted graph, and for an undirected and unweighted graph, Thorup's 1999 $O(E)$ algorithm is faster even though it's capable of handling arbitrary natural number edge weights? This seems surprising to me.
To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the &quot;source&quot; node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time.
It follows since the graph BFS traverses is guaranteed to be connected, hence $\forall v:deg(v)\ge 1$. Thus $|E_{traverse}| \ge \frac{|V_{traverse}|}{2}$ where $E_{traverse}$ and $V_{traverse}$ are the sets of edges and vertices the BFS &quot;saw&quot; while running.
Clearly, the BFS works in $O(|E_{traverse}|+|V_{traverse}|)$ but since $|V_{traverse}|=O(|E_{traverse}|)=O(|E|)$, we can conclude that the BFS instance runs in $O(E)$.
Note: This is only true if the BFS is ran only from one source, unlike the usual BFS algorithm description that starts the traversal from a node we didn't mark yet if we finished the last traversal instance.

Honestly, I don't know about Thorup's algorithm, so I can't answer this part of the question about it. However, I know that BFS works for both directed and undirected graphs, but doesn't work with natural weights.