# What algorithm should I use to find the shortest path in this graph

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?

-

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

-
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 – user2791940 Jan 14 '14 at 16:12
@user2791940 just have set all weights equal to 1 – ratchet freak Jan 14 '14 at 16:14

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. – Steve Evers Jan 19 '14 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. – LP_ Jan 20 '14 at 7:48
Very true! My mistake. – Steve Evers Jan 20 '14 at 16:11