BFS Shortest Path

[assimiz]

Hi,
Do you think a BFS shortest path implementation would be useful?
Cause currently one is bound to use Dijkstra/others also for unweighted graphs and BFS would perform much better in this case.

Regards,
Assaf.

[abhishekiit2014032]

This could be solved easily using (BFS) if all edge weights were (1)
Dijkstra can be used only when edge weights are +ve
best-known algorithm for finding single-source shortest paths in a directed graph with negative edge weights is the Bellman-Ford algorithm. This comes at a cost, however: Bellman-Ford requires O(|V|·|E|) time, while Dijkstra's requires O(|E| + |V|log|V|) time, which is asymptotically faster for both sparse graphs (where E is O(|V|)) and dense graphs (where E is O(|V|^2)).

[assimiz]

Yes @abhishekiit2014032 that's exactly what I am talking about. A BFS shortest path implementation.

[swetanjal]

@assimiz I am interested to implement this.
I would be grateful if you guide me how to go about doing it as I come from competitive programming background and this will be my first contribution to any open source organization.

[NorahS]

Hi, I'd like to try and implement this as well

[divyanshu132]

If this issue has not been resolved, I'll be happy to resolve it. Should I proceed??

[jsichi]

Sure; please start here:

https://github.com/jgrapht/jgrapht/wiki/Become-a-Contributor

[divyanshu132]

Hi, @jsichi I've implemented it and created a pull request please have a look.

[ksskreddy]

Hi,is it still open?I would like to implement it

[jsichi]

Yes, it's still open. (The previous submission wasn't usable.)