Optimizing Bellman Ford algorithm

Bellman Ford algorithm is used to find single source shortest path. In this algorithm, we try to relax each edge n-1 times where n is the number of vertices. Instead of running the code for each edge again and again, we can relax only those edges which are connected to the vertex which was relaxed in the last iteration.

Link to code.

Priority queue using heap

The code uses a max heap to remove the maximum element present in the data. Heap is used as it helps to perform the above operation in O(log n) time.
Link to code.