Before revision:  All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space  .
After revision:  All of our algorithms can be used to approximate the hyperbolicity of a geodesic metric space . We also show that a similar characterization of hyperbolicity holds for all geodesic metric spaces endowed with a geodesic spanning tree. Along the way, we prove that any complete geodesic metric space (X,d) has such a geodesic spanning tree. We hope that this fundamental result can be useful in other contexts .