Siguiendo tu notación, efectivamente Dijkstra tiene complejidad cuadrática sobre los nodos en su implementación directa. Si lo implementas con colas de prioridad con coste logarítmico, bajas la complejidad a O((n + a)logn), que es la complejidad de BFS con un factor logarítmico extra (programándolo bien, obviamente).

Si el grafo es completo, i.e. a = n², uno quedará O(n²logn) y otro O(n²), que evidentemente es mejor.

Esto hablando de las versiones estándar de cada uno. Si se quiere rizar el rizo y hablar de la versión de Dijkstra con Fibonacci Heaps, que rara vez se usa a la práctica, entonces se acaba teniendo una complejidad teórica (no hablemos ya de las constantes debidas a implementación) de O(a + nlogn), que sigue siendo peor que un BFS.