0
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" 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 "saw" 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Don't you need a boolean array of size $|V|$ to know which vertices have been visited? Wouldn't that mean that BFS is $O(|E| + |V|)$ (which is $\neq O(|E|)$ in a graph with few edges)? $\endgroup$
    – Nathaniel
    Apr 23, 2021 at 22:35
  • $\begingroup$ Well I guess it could be done with a hashtable data structure, to test in $O(1)$ average case if a vertex have been seen, but I must admit I always use boolean arrays. (And with hashtables, the worst case would be $O(|V|^2)$, not $O(|E|)$.) $\endgroup$
    – Nathaniel
    Apr 23, 2021 at 22:37
  • $\begingroup$ I totally agree with you. This would work for expected $O(|E|)$. But there is a better way to know if a vertex has been seen: To the description of the vertex add a boolean that is set to true when we see the vertex. The graph is initialized such that all vertices have this boolean set to false at the beggining. This is a roundabout way of doing this, but it definitely works for worst case $O(|E|)$ instead of average case. $\endgroup$
    – nir shahar
    Apr 23, 2021 at 22:51
  • $\begingroup$ This would still have some problems with it, such as assuming the input has extra data slots in each vertex that we can store stuff in. $\endgroup$
    – nir shahar
    Apr 23, 2021 at 22:52
  • $\begingroup$ So Wikipedia is wrong and BFS is actually only $O(E)$? The other answer seems to suggest the opposite resolution? $\endgroup$
    – tparker
    Apr 24, 2021 at 3:40
0
$\begingroup$

I have looked up a little bit about Thorup's algorithm (see here), but it turns out that:

For simplicity, we assume […] that the input and output size is $O(m)$

Here, $m$ is the number of edges $|E|$. This assumption in fact proves that a hypothesis for the proof is $|V| = O(|E|)$ (since $V$ is part of the input).

That means that even Thorup's algorithm runs in time $O(|V| + |E|)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So Wikipedia is wrong and Thorup's algorithm is actually $O(V+E)$ in general? The other answer seems to suggest the opposite resolution? $\endgroup$
    – tparker
    Apr 24, 2021 at 3:41
  • $\begingroup$ I highly doubt that for this particular problem, Thorup's algorithm actually needs to go through all vertices. A similar argument to what I gave in my answer will show that we only need to search in $|V_{traverse}|=O(|E|)$ vertices. I don't know about the details of Thorup's algorithm, but can't you construct a similar proof here? $\endgroup$
    – nir shahar
    Apr 24, 2021 at 9:23
  • $\begingroup$ Didn't read the details, so I wouldn't really know, but I think you are right, and the answer is the same for both cases: $O(|E|)$ if the data structure is adapted to the problem, $O(|V| + |E|)$ otherwise. $\endgroup$
    – Nathaniel
    Apr 24, 2021 at 14:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.