0
$\begingroup$

I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and so on. Note that the number of goal nodes will not be very big.

If I were looking for only one path I would use BFS. But I'm quite sure how I can use BFS to find all paths to goal nodes.

Time is of the essence here so I wanted to use one BFS call to find all paths at once. I basically only need their costs. But I don't really know how to do that.

Does Dijkstra's algorithm do that?

The ultimate goal is that for every source node(because there are more of them) find the shortest paths to goal nodes. All sources want to find paths to the same goal nodes. And based on every path cost I want to create a consistent bipartite graph.

Improve this question
$\endgroup$
2
  • $\begingroup$ Are you sure you want all shortest paths? There can be exponentially many, so in the worst case you won't be able to output them all within your lifetime. What are you going to do with that many paths? Perhaps you have some other ultimate goal that would be better to address directly? Do you want all shortest paths, or all paths? $\endgroup$
    – D.W. ♦
    Apr 1, 2020 at 17:50
  • $\begingroup$ @D.W. I updated the question so maybe now it's clearer. $\endgroup$
    – Karol
    Apr 1, 2020 at 17:53

1 Answer 1

Reset to default
1
$\begingroup$

Use BFS, and keep prev pointers. Good textbooks will have a chapter on shortest-path algorithms where they describe how to reconstruct the paths themselves (not just the distances) using prev pointers; use that method, and then you'll be able to reconstruct a shortest path from $X$ to any other node. Initially the estimated distance to all nodes is $+\infty$. Whenever you update the distance to something lower, update its prev pointer to point to the node where you came from.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, it's basically Dijkstra's algorithm but for all weights 1? $\endgroup$
    – Karol
    Apr 1, 2020 at 18:09
  • $\begingroup$ @Karol, BFS is related to Dijkstra's algorithm, but you don't need a priority queue. $\endgroup$
    – D.W. ♦
    Apr 1, 2020 at 18:13
  • $\begingroup$ Yes yes, I know that. But thanks a lot, I couldn't wrap my mind around it. $\endgroup$
    – Karol
    Apr 1, 2020 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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