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?
Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this communityYou 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*).
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.