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 ?
