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!

Answer 1

[Walter Roberson]

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.

[Phillipp]

Yes that is exactly what I said in my question. I want the undirected shortestpath in this directed graph.

[Walter Roberson]

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]

Okay I will try this later today.