List of paths between two points
4 次查看(过去 30 天)
显示 更早的评论
I have a list of "Start point" and "End point", and I want to find all shortest paths between a point (let's say the first one) and every other point, there is maximum steps to avoid infinit looping.
Shortly, what I do now is creating a matrix by duplicating all single paths up to the "maximum steps" value, and then looping on steps then selecting for every "End Point" the lines that end with it (the end point) if exists.
For a list of 2^6 * 7 elements, there's 7^6 lines on the resulted matrix, but for 2^n * (n+1) there's n^(n+1) lines. I understand that this is sligntly analogic to the travelling salesman problem, but I just want to know if there's a more economic process to do this. and I only need it to run to the n=20, now I can's go further 6
here's my sample data. Thanks
0 个评论
采纳的回答
Walter Roberson
2019-11-10
TR = shortestpathtree(G,s) returns a directed graph, TR, that contains the tree of shortest paths from source node s to all other nodes in the graph. If the graph is weighted (that is, G.Edges contains a variable Weight), then those weights are used as the distances along the edges in the graph. Otherwise, all edge distances are taken to be 1.
3 个评论
Walter Roberson
2019-11-10
The start points and end points and other distinguished points would be the nodes. The connections between them would be the edges.
For example if you have two cities that are of interest, then those would be nodes, and if you abstract away the road between them to just a distance number and the fact that the road exists, then the connection would be edges.
Intersections are always nodes -- stopping points or switching points. Things you travel along are edges.
更多回答(1 个)
Thiago Henrique Gomes Lobato
2019-11-10
It is not so clear by your list what underlying process you have, but I may assume you have a map (graph) where each point is a node and the nodes are connect by some distance metric (edge) and you want to find the way that minimizes that metric. This is basically a description of a path finding problem. For it there exist some algorithms that do it relatively efficiently as the Dijkstra or A*, they will surely be more memory and time efficient as to list all possible paths .
Here are some links that I founded in file exchange for matlab implementations (I didn't test myself, but should at least give you a direction):
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!