How to obtain shortest paths with parents in a weighted directed graph?
17 views (last 30 days)
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.
Avni Agrawal on 27 Sep 2023
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.