Iteration related to Dijkstra function issue

2 次查看（过去 30 天）
Nuno Palma
Nuno Palma 2016-12-12
评论： Christine Tobler 2016-12-13
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?

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

采纳的回答

Steven Lord
Steven Lord 2016-12-12
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."
  2 个评论
Nuno Palma
Nuno Palma 2016-12-12
Sadly i cant use this function on my project. Any other suggestion?
Christine Tobler
Christine Tobler 2016-12-13
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.

请先登录，再进行评论。

更多回答（0 个）

类别

在 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