I have a problem about the calculation of shortest paths on an unweighted and undirected graph.
Which algorithm I use to calculate the shortest path between a node A and node B that passing through a node C on an undirected and unweighted graph?
Add a comment
|
2 Answers
You can split the solution into 2 steps, first find a path from A to C, and then find one from C to B and concatenate them.
To find the individual paths you'll want to use Dijkstra (given that unweighted likely means there is no heuristic to get for A*).
answered Jan 14, 2014 at 15:57
-
Thank you for you're idea.Dijkstra uses weighted graphs and oriented. I will try to adapt it to my case, it should not be difficult Jan 14, 2014 at 16:12
-
2
Like ratchet freak pointed out, you'll have to split the solution into finding a path from A to C and then from C to B.
However, Dijkstra is not needed since the graph doesn't have any weight. A simple Breadth First Search (BFS), slightly easier to implement, is enough.
Also, if you were to implement A*, no weight doesn't mean that you cannot find a heuristic. You could still favor paths that go through nodes with a certain property as a heuristic.
-
DFS (or, slightly more complicated, iterative DFS) doesn't run into the memory issues that arise using BFS on some types of graphs. It also depends on the characteristics and expectations of the graph/data though. Jan 19, 2014 at 21:46
-
A DFS won't give you the shortest path, so it's not a correct solution for this problem. And if you implement the DFS using recursion, you can also get memory problems arising from stack overflow. Jan 20, 2014 at 7:48
-