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?

CodePudding user response：

For the given properties of the unweighted graph: