The First 10 Shortest Paths In A Graph - Igraph 0.6 - Python 2.7

I was wondering about this ever since I've started to successfully implement Igraph into my coding: Can you retrieve with get_all_shortest_paths as many shortest paths as you like.

Solution 1:

Okay, I'm still unsure what you mean by the "first 10 shortest paths", but here is what I think you might want to achieve. You have a graph where the edges are labeled by the actual (say, Euclidean) distance of the two endpoints. You are given two points, and you wish to find a few alternate paths between them while trying to keep these paths as short as possible. Note that since your graph is weighted, it is very unlikely that you will have many shortest paths between two points - in order for all of the paths to be the shortest, they must have exactly the same total weight. If your weights measure actual distances "as the crow flies", it is very unlikely that such a co-occurrence ever happens - the ten paths you would be looking for would have slightly different lengths. So, get_all_shortest_paths is not useful to you, not only because it does not use weights, but also because even if it did, you are unlikely find multiple paths between two points that have exactly the same length.

An alternative is get_shortest_paths, which can consider weights, but it will return only one path between a pair of vertices. (The reason why it is called get_shortest_paths is because it returns multiple paths if you specify multiple target vertices - more precisely, it gives you one path for each target vertex). So, you cannot use get_shortest_paths to obtain the ten paths you are looking for.

After some googling, I have found an implementation of the k-shortest-paths algorithm that might be useful for you. It is not part of igraph, but you can save your graph from igraph, call out to the compiled executable of the k-shortest-paths algorithm using os.system or the subprocess module in Python and then parse the result somehow.