2

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?

2 Answers 2

4

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*).

2
  • 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
    @user2791940 just have set all weights equal to 1 Jan 14, 2014 at 16:14
3

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.

3
  • 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
  • Very true! My mistake. Jan 20, 2014 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.