Can I get all of the shortest paths between all pairs of nodes in a Directed Graph in one function call

I need to store all of the shortest paths between nodes in a directed tree of over 3000 nodes and 900000 edges.

The edges have weights - the shortest path is the one with the lowest summed weights.

I want every series of nodes from source to target traversed by the path and its length

Using a loop as follows takes many hours - I did not let it finish.

Here is the code

p_all = cell(num_nodes * num_nodes, 1);

for i = 1:num_nodes

for j = 1:num_nodes

[p, d] = shortestpath(g, i, j)

index = (i-1)*num_nodes + j;

p_all{index, 1} = [p, d];

end

end

Note that the calculation of betweenness centrality only takes 30 seconds. This also needs all of the shortest paths!

I believe that making N^2 individual calls is very inefficient as information that could be used in other calls is thrown away each time. What I need is a function that will compute all of the shortest paths in one call. I have tried this function which gives me all of the shortest paths from a starting node. But I do not understand the output and it does not seem to take into account the weights.

p_all = cell(num_nodes, 1);

for i = 1:num_nodes

[p, d] = shortestpathtree(g,i);

end

I have also looked at the NOCAD library - there is a function called allShortestPaths but it does not actually return the nodes of the paths, just the lengths.

Anyone have any suggestions ?

[Christine Tobler]

You say your digraph is a "directed tree of over 3000 nodes and 900000 edges". A tree would have one less edge than it has nodes. Is your digraph an acyclic digraph (a directed graph that contains no cycles).Or is it a generic directed graph that may contain cycles?

Second question: Are any of the weights negative?

[Christine Tobler]

On second thought, your digraph definitely has cycles, as every node is connected to every other node by an edge (9000000 = 3000^2).

This makes the question of if there are negative weights more important: If there are negative weights, for performance you may need to use Johnson's algorithm to find an alternative set of edge weights that are all non-negative. This will allow each loop iteration to use Dijkstra's algorithm instead of the much more expensive Bellman-Ford.

I can give more details but want to wait if the problem even applies.

[Dominic O KANE]

There are no negative weights. And the exact numbers are

Num Nodes 3015

Num Edges 8954550

There are no self-edges. I have tried the Bellman Ford in the links provided and it does not work. So would be happy to have other suggestions.

Thanks.

[Christine Tobler]

Hi Dominic,

All right, in that case most (98%) of nodes are connected by an edge then.

Since there are no negative weights, no complications should arise and you do not need to worry about Bellman-Ford algorithm. The answer I provided below should work for you.

Answer 1

[Christine Tobler]

Using shortestpathtree in a loop over the starting node is the way to go. You can change the data format of the first output by using the OutputForm Name-Value Argument to "cell" or "vector".

• The "cell" option should allow you to compute the cell array of all nodes on the path between any pair of nodes, by calling it in one loop over all nodes like you mention above.
• The default output is a tree of only the shortest paths - this is of course not very useful when your graph is already a tree - its use is for example to plot which paths would be taken from the start node to every other node in a non-tree graph.
• The "vector" option is most efficient for storage, and is basically what "betweenness" centrality would be using internally. This is a vector which, for every node, contains the next node on the path to the starting node. Whether you can use this will depend on what your next step with your cell array of paths will be.

That is, you can use

d = zeros(num_nodes, num_nodes);
p = cell(num_nodes, num_nodes);
for i = 1:num_nodes
    [p(i, :), d(i, :)] = shortestpathtree(g, i, OutputForm="cell");
end

[Dominic O KANE]

Thanks a lot. I already coded it up and it's running ! It will take a while but minutes rather than hours :-).

PS I think p_all should be p in your code.

PPS It's a lot of data. What's the best way to save it to file ?

[Christine Tobler]

Fixed, thanks!

If you want to save it as cell array, there isn't much to do besides a .mat file. The data can be expressed more compactly as just a num_nodes x num_nodes matrix if you use the "vector" representation, but whether this is something you can then use depends on what you do with the data.