best algorithm for finding distance for all pairs where edges' weight is 1

Question

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!

Answer 1

There is space for improvement because in unweighted graphs, you gain an additional attribute which does not hold for weighted graphs, namely:

For any edge directly connecting A to C, you know for sure that there is no shorter path via a third node B.

With this in mind, you should be able to simplify Dijkstra's Algorithm: As you may know, it works with three sets of nodes:

1. Those of which the definitive shortest path is known,
2. those of which a preliminary distance has been calculated and
3. those which have not yet been explored.

When following an edge e from A (1.) to C (3.), original Dijkstra would move node C from (3.) to (2.). Since the above attribute holds in all your graphs, you can however add it directly to the set (1.), which is more efficient.

Here's the essential observation: The procedure outlined above is basically a BFS (breadth first search), i.e. you can find the distance from some fixed node v to any other node in O(|V| + |E|).

You did not mention in your original question that the graph was basically a grid with some holes in it. This is an even stronger requirement, and I am sure you can exploit it. Doing a quick search for "grid graph shortest path" yields this paper which promises O(sqrt(n)) in the best case. As the problem you specify is fairly well-structured, I'm almost sure there are several more papers which you might want to look into.