Shortest Paths

Dijkstra's Algorithm is not guaranteed to produce the shortest path if the edge weights are negative.

O((n+m)log(n)) is the time complexity of Dijkstra's alg (n=number of nodes, m=no of edges, log(n)=heap sorting whereas O((n+m)) is the time complexity of BFS.

Negative weight cycle

When a graph has negative weight cycle, then the problem is not well-defined anymore. So, lets generalize the problem and find a negative weight cycle if one exists. If one doesn't exist, we'll solve the shortest path problem.