Use a Queue or PriorityQueue for traversal.

Can be used to find the shortest paths in graphs.

If negative edges are present keep calling update V-1 (V is the number of vertices) to get the shortest path. If on Vth iteration the distances still reduce that means there are -ve cycles.

**Implementation Note:**

Queue can be implemented using an array. children for j are 2j+1 & 2j+2 (0 based index) and parent of j is floor(j/2) if j is odd or floor(j/2) -1 if j is even. This is better for dense graphs.

Binary Heap based implementation. This is better for sparse graph’s. insert/decrease key is log(V) and deleteMin is log(V)

Java Priority Queue has no provision for decreasing the key and is based on array implementation.

one set of methods (peek, poll) return nul if no element and (remove, element) throw NoSuchElement if no element is present when operation is performed.

### Like this:

Like Loading...

*Related*