Iteration related to Dijkstra function issue

So, I used a function, similiar to Dijkstra's to calculate the shortest paths in relation to a certain matrix. One of the output variable I got was an array with the previous vertices in the shortest paths.

For example, starting from the first node: previous = [ 0 1 1 3 6 3 ]. Being the first index the previous node before reaching node 1, which is 0 as it's the node itself. The second index, the previous node before reaching node two, which is node 1.

The result I'm looking for is the paths it takes to reach each node. Something like this: For node 2 -> [1 2], for node 3 -> [1 3], for node 4 it'd be [1 3 4], for node 5 [ 1 3 6 5] and for node 6 [1 3 6].

So, to obtain that result, right now the only solution I see, is get the indexes for each previous path and then see which index has that value. For that I'd need to use the function "find()" but since some of the indexes have the same numbers I can't really do that.

Any other solution?

Answer 1

[Steven Lord]

Consider using the shortestpathtree method for graph and digraph objects. Specifying the 'Method' as 'positive' creates the tree using "Dijkstra algorithm that requires all edge weights to be nonnegative."

[Nuno Palma]

Sadly i cant use this function on my project. Any other suggestion?

[Christine Tobler]

The method shortestpathtree has options to both compute the vector you described, or a cell array containing the paths you are trying to retrieve. You could take a look at the MATLAB code for how one is translated to the other, using edit shortestpathtree. See the subfunction constructTree.