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

7 次查看（过去 30 天）
Andres Salomon Fielbaum Schnitzler
评论： Andres 2023-9-28
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.

请先登录，再回答此问题。

回答（2 个）

Steven Lord
Steven Lord 2023-9-27
You may want to use the shortestpath or shortestpathtree functions instead of distances for this use case.
  2 个评论
Christine Tobler
Christine Tobler 2023-9-27
Ran in:
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
Andres 2023-9-28
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
Avni Agrawal 2023-9-27
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.

类别

在 Help Center 和 File Exchange 中查找有关 Dijkstra algorithm 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by