Single source shortest path in JGraphT for unweighted graph

1
votes

JGraphT has many implementations for shortest paths (Dijkstra, Belman Ford and more)

I need a single source shortest path for an unweighted graph.

Here are my questions (specific to JGraphT):

  1. First, I assume that using Dijkstra for unweighted graphs is wasteful (uses a priority queue which has slower queue deque than a regular queue that BFS uses, and since on unweighted graph all weights are 1, this is not really adding any value). Is my assumption correct?

  2. Assuming the answer to 1 is "yes", then I assume I'll use BreadthFirstIterator other than rolling my own, (unit tested, and as simple BFS is, I'm sure I'll have some corner case bug, even Java's binary search had an integer overflow thank's to a bug that Josh Bloch himself introduced and it wasn't solved until 2006!). But the question is, there is still a (very small) step to take from a raw BFS to actually getting the single source shortest paths, should I write my own UnweightedSingleSourceShortestPaths class? or is there one hidden in JGraphT core library that I can just plug into?

1
javaalgorithmgraphshortest-pathjgrapht
In case of unweighted graph, all edges have the same weight, so the priority queue won't be relevant, Dijkstra in that case will be simple BFS on the graph. - Maroun
Yes, but if Dijkstra uses a heap priority queue, queue and dequeue are O(LogN) no? So if I do a Dijgstra for an unweighted graph vs do a BFS do the same graph, won't the BFS be faster? (although they both will give me the same results...) - Eran Medan

1 Answers

0
votes

Since I think I found the answer to the 2nd question, I think it also answers the 1st question (if JgraphT's Dijkstra was the most efficient for the simple case of all weights = 1, then why would CDK create their own?)

Here is the answer to #2 - yes, there is an open source (LGPL) solution: https://github.com/cdk/cdk/blob/master/legacy/src/main/java/org/openscience/cdk/graph/BFSShortestPath.java