How to obtain shortest paths with parents in a weighted directed graph?

1 view (last 30 days)
Commented: Andres on 28 Sep 2023
Hi,
I have recently discovered the function distances in Matlab, and realized that it works very well and fast. I give it as input a weighted directed graph, and outputs the shortest distance between each pair of nodes. In my case, I need to obtain not only such distances, but also the parents, that is, if my graph has N nodes, I want as an output an P of size NxN, such that P(i,j) says which is the last node before j in the shortest path from i to j.
Do you know if there exists such a function? I've found functions that return the whole route, but for a given i,j, and running them N^2 times is extremely slow.

Steven Lord on 27 Sep 2023
You may want to use the shortestpath or shortestpathtree functions instead of distances for this use case.
Christine Tobler on 27 Sep 2023
Yes, you can call shortestpathtree in a loop:
g = digraph([1 2 3], [2 3 1]);
n = numnodes(g);
P = zeros(n);
for ii=1:n
P(ii, :) = shortestpathtree(g, ii, OutputForm='vector');
end
P
P = 3×3
0 1 2 3 0 2 3 1 0
Andres on 28 Sep 2023
Thanks! This works beautifully! I was using a Dijkstra implementation I found online before. For a graph with 4k nodes and 9k arcs, your code has reduced the running time from 6 hours (with 50% of chances of crashing) to 5 seconds.

Avni Agrawal on 27 Sep 2023
Hi,
I understand that you are trying to find any in-built function to compute parent node.
Unfortunately in MATLAB, there is no built-in function specifically designed to compute the parent nodes for all pairs of nodes in a weighted directed graph. The distances function in MATLAB computes the shortest distances between all pairs of nodes, but it does not directly provide the parent nodes.
To obtain the parent nodes, you would need to modify or extend the existing functions or implement your own algorithm. The most common approach is to use graph traversal algorithms like Dijkstra's algorithm or the Bellman-Ford algorithm to compute the shortest paths and extract the parent nodes along the way.
I hope this helps.