Use Shortest path in directed graph
显示 更早的评论
Hello,
I have a Graph that has a few nodes and edges. There is actually a specific reason to not use an undirected graph but a directed one. In this example I need to find the shortest path in between Node 8 and Noe 6. I know that there is no actual right way to solve it, because it is a directed graph.
But I actually need the directed graph for other parts of the calculation, so I cannot change that. Is there a workaround for this problem?
Thank you in advance!
回答（1 个）
Walter Roberson
2020-5-13
1 个投票
No, there is no solution to that.
If you start at node 8, then you can move to node 4 or node 7. However, both of those nodes have only inputs and no outputs, so you cannot move from 4 or 7 to anywhere else.
If you start at node 6, then instead of going through a number of steps to prove that no path works, just look at the destination node 8 and notice it has no inputs, so there is no way to reach it from node 6.
Thus, if you start at 8 you cannot get to 6, and if you start at 6 you cannot get to 8.
Therefore there is no directed path between node 6 and node 8.
3 个评论
Phillipp
2020-5-13
Walter Roberson
2020-5-13
Let your current directed graph be G. Then
uG = graph(G.Edges); %creates an undirected graph
Now you can run the shortest path algorithm on uG.
Note: when you construct the undirected graph this way, then any weight information in the original graph is carried over.
Phillipp
2020-5-13
类别
在 帮助中心 和 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!
Translated by 
