Most efficient (Big O) algorithm for finding the shortest path between two nodes in an unweighted directed graph

0
votes

I am looking for the most efficient algorithm, according to the Big O Notation, to find the shortest path between two nodes in an unweighted directed graph.

I am mostly split between Dijkstra's with heaps, which I would normally use if the graph was weighted, and breath-first search.

Does the graph being unweighted make Dijkstra's less efficient to use in this situation than BFS?

2
algorithmgraphpathbig-o
Search for the respective complexities of Dijkstra's and BFS. - Abhishek Bansal
BFS's complexity - O(E+V) does indeed seem to be better than Dijkstra's. What I want a confirmation of, I guess, is if BFS is the optimal algorithm for this problem, or if there is some other algorithm I haven't thought of, which is even more efficient. - Brandon Heat

2 Answers

0
votes

There is no known algorithm that can outperform Breadth First Search for single source, single destination optimal shortest path in an unweighted graph (regardles of whether it's directed or undirected) in the general case.

However, if you have a special case, where you can provide an admissible heuristic, you would be able to implement a more efficient search using A* search.

2
votes

According to Wikipedia,

Single-source Shortest Path

  • BFS - O(V + E)
  • Dijkstra (With List) - O(V²)
  • Dijkstra (With Modified Binary Heap) - O((E+V)logV)
  • Dijkstra (With Fibonacci Heap) - O(E + VlogV) - Fredman & Tarjan Implementation
  • Dijkstra (With Fibonacci Heap) - O(EloglogV) - Johnson, Karlsson and Poblete Implementation

The time complexity of A* depends on the heuristic. In the worst case of an unbounded search space, the number of nodes expanded is exponential in the depth of the solution (the shortest path) d: O(bd), where b is the branching factor (the average number of successors per state).

Choose the one that suits you the best.