Djikstra's shortest path vs Brandes algorithm for betweeness centrality
The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph.


This isn't necessarily true. Perhaps there is a different algorithm that is faster than what you outline. One possible explanation for the discrepancy in running times is that the NetworkX library uses a smarter algorithm. However, it's hard to know because you haven't told us how the function betweenness_centrality is implemented in NetworkX. It is also possible that it uses an algorithm along similar lines, but employs some optimizations that don't affect the asymptotic running time (big O) but does save a large constant factor.