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

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.

Answer 1

[Steven Lord]

You may want to use the shortestpath or shortestpathtree functions instead of distances for this use case.

[Christine Tobler]

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]

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.

Answer 2

[Avni Agrawal]

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.