フィルターのクリア

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

13 ビュー (過去 30 日間)
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 件のコメント
Dominic O KANE
Dominic O KANE 2024 年 1 月 24 日
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 2024 年 1 月 24 日
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.

サインインしてコメントする。

回答 (1 件)

Christine Tobler
Christine Tobler 2024 年 1 月 24 日
編集済み: Christine Tobler 2024 年 1 月 24 日
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 件のコメント
Dominic O KANE
Dominic O KANE 2024 年 1 月 24 日
編集済み: Dominic O KANE 2024 年 1 月 24 日
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 2024 年 1 月 24 日
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.

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeGraph and Network Algorithms についてさらに検索

製品


リリース

R2023b

Community Treasure Hunt

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

Start Hunting!

Translated by