From Jon Snow to Three Eyed Raven of Tech Interview preparation Part I

Djikstra Algorithm

We all know what Djikstra’s algorithm does.

Given a Graph with edges connecting two nodes in a graph, find the shortest path from A to B.

Before we start processing this graph, we need to know few things.

1. No duplicate edges between nodes
2. If we have multiple edges, then select the smallest one
3. NO negative edge weights

Once we are done with this changes, we are ready to process this graph.

We create an Adjacency List representation using LinkedList of LinkedList, I prefer LinkedList because of no index based traversal, though ArrayList can be preferred as it’s an Array Backed store.

Now we need to have one more auxiliary Data structure that is of Visited array, for all the nodes it keeps track of how many nodes has been visited.

The concepts is very much similar to DFS but with one twist, i.e. selection of next node.

In Djisktra’s algorithm we need to check the node which hasn’t been visited yet, and find the smallest among them. If no such node exists, iterate over , i.e starting from root, take another search tree.

For selection of edge with shortest distance, we usually use heaps. The advantage of heap is, as we iterate through the neighboring nodes and input its distance to the heap, it automatically puts the smallest node on top. So as we remove the topmost element, and check if its visited, subsequent removal will give us the next smaller element.

Instead of heap, we can put all the adjacent elements in the array and sort it and get the smallest element starting from index 0 as well. This is also an approach.