Running Time of BFS vs Dijkstra

Question

I have a unweighted, connected graph G with n vertices and m edges.
m=O(n log n).
I want to find the shortest path from vertex s to vertex v.
I want to know if a BFS traversal or Dijkstra's algorithm would be asymptotically faster.

BFS would start from s. Dijkstra's algorithm, starts from s, and implements a Fibonacci heap.

The running time of BFS is Θ(n+m) = O(n+n log n) = O(n log n)
And the running time of Dijkstra is O(m+n log n) = O(n log n+n log n) = O(n log n)

So are both algorithms, for this problem, asymptotically as fast, or am i missing something?

Answer 1

For the given properties of the unweighted graph:

• 𝐺(𝑉,𝐸) is connected, and
• |𝐸| ∈ θ(|𝑉|log|𝑉|)

...we can indeed derive a time complexity of 𝑂(|𝐸|) for both BFS and Dijkstra's algorithm with Fibonacci heap.

Just an additional note:

The phrase "asymptotically as fast" does not mean that there is an input size above which both algorithms will run just as fast. It means that for large enough inputs the ratio of their running times (on the same computer) will remain within a constant min/max range.

As Fibonacci heaps have quite some overhead and BFS just needs a simple queue or two arrays, there is no doubt that this bounded ratio will be in favor of BFS.