The “Important Algorithms Capsule” : Part-2

We have already learnt about Floyd Warshall Algorithm to find shortest distance between all the points in any weighted-directed graph in previous Part. Here we are going to learn about another algorithm which solves the problem of finding shortest distance between all the points from a source point in any graph in O(n²) or O(ElogV) time complexity but with limitations.

Note : Most of the cases can be solved by the following algorithm except those graphs who have negative edge weights and cycles.

DIJKSTRA ALGORITHM : Min heap implementation

Here we define a wrapper class for Graph. We consider having adjacency list representation of the graph. We use a priority queue to generate the instances of vertices and update the distance for every vertex u from priority queue pq considering :

if(distance[u]+weight(edge to v)<distance[v]) :

distance[v]=distance[u]+weight(edge to v)

Why Priority Queue ?

Whenever distance of a vertex is reduced, we add one more instance of vertex in priority queue (even if it already exists in the queue). We only consider the instance with minimum distance and ignore other instances.

Dijkstra implementation

Yay, we made it till here !! Let’s practice few questions and brush up the knowledge.

1. Path-with-maximum-probability
2. Network-delay-time
3. Path-with-minimum-effort
4. Find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance

We discussed a limitation of this algorithm in the beginning of the article, remember ! We’ll come up with another algorithm that is capable of helping us out with it ;)

Till then ….Happy Coding :)