Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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

share|improve this answer
    
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 at 16:12
2  
@user2791940 just have set all weights equal to 1 –  ratchet freak Jan 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.

share|improve this answer
    
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 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 at 7:48
    
Very true! My mistake. –  Steve Evers Jan 20 at 16:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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