store path of minimum spanning tree
1 次查看(过去 30 天)
显示 更早的评论
hi,
i a 14 node system and i want minimum spanning tree from one node to some of the nodes but not all the nodes. at the moment am able to get minimum spanning tree of all the nodes. also is possible to get a full path from one node to the other node instead of the predecessor table?
thanks
0 个评论
采纳的回答
Steven Lord
2019-8-1
Use the shortestpath or shortestpathtree functions for graph and digraph objects.
9 个评论
Steven Lord
2019-8-6
Suppose the graph whose spanning tree you're trying to compute is this:
G = graph(ones(5)-eye(5));
plot(G)
One path from 1 to 3 is the edge (1, 3).
Another path from 1 to 3 is (1, 2), (2, 4), (4, 5), (5, 3).
Another path from 1 to 3 is (1, 2), (2, 4), (4, 5), (5, 2), (2, 4), (4, 5), (5, 3).
I can go around that cycle between 2, 4, and 5 an arbitrary number of times before continuing to 3 if I want. So there are an infinite number of possible paths.
Why might you want to go around that path repeatedly? Assume the nodes are cities and taking a path means going on a sales trip. If you make a profit transporting goods from 2 to 4, resupply at 4 and make a profit transporting other goods from 4 to 5, then resupply at 5 and make a profit transporting a third set of goods from 5 to 2 you could continue the cycle accumulating your profits. Even if one or two of the legs costs you money, if the total cost of the trip earns you money why not?
Since you mention your graph or digraph comes from a Simulink model, one type of cycle like that is called an algebraic loop.
Maybe if you tell us a little more about your ultimate goal we can offer suggestions for how to achieve that goal, even in the potential presence of an algebraic loop.
更多回答(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!