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

7 visualizzazioni (ultimi 30 giorni)
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 ?
  4 Commenti
Dominic O KANE
Dominic O KANE il 24 Gen 2024
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
Christine Tobler il 24 Gen 2024
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.

Accedi per commentare.

Risposte (1)

Christine Tobler
Christine Tobler il 24 Gen 2024
Modificato: Christine Tobler il 24 Gen 2024
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
  2 Commenti
Dominic O KANE
Dominic O KANE il 24 Gen 2024
Modificato: Dominic O KANE il 24 Gen 2024
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
Christine Tobler il 24 Gen 2024
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.

Accedi per commentare.

Categorie

Scopri di più su Graph and Network Algorithms in Help Center e File Exchange

Prodotti


Release

R2023b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by