best algorithm for finding distance for all pairs where edges' weight is 1
I'm assuming the graph is dynamic; otherwise, there's no reason not to use Floyd-Warshall to precompute all-pairs distances on such a small graph ;)
Suppose you have a grid of points (x, y) with 0 <= x <= n, 0 <= y <= n. Upon removing an edge E: (i, j) <-> (i+1, j), you partition row j into sets A = { (0, j), ..., (i, j) }, B = { (i+1, j), ..., (n, j) } such that points a in A, b in B are forced to route around E - so you need only recompute distance for all pairs (a, b) in (A, B).
Maybe you can precompute Floyd-Warshall, then, and use something like this to cut recomputation down to O(n^2) (or so) per graph modification...
As the title said, I'm trying to implement an algorithm that finds out the distances between all pairs of nodes in given graph. But there is more: (Things that might help you)

The graph is unweighted. Meaning that all the edges can be considered as having weight of 1.
|E| <= 4*|V|
The graph is pretty big (at most ~144 depth)
The graph is directed
There might be cycles 
I'm writing my code in python (please if you reference algorithms, code would be nice too :))

I know about Johnson's algorithm, Floyd-Warshal, and Dijkstra for all pairs. But these algorithms are good when the graph has weights.
I was wondering if there is a better algorithm for my case, because those algorithms are intended for weighted graphs.
Thanks!