Understanding Dijkstra’s algorithm

Dijkstra belongs the class of greedy algorithms that gives single source shortest paths in a weighted undirected graph.


Step 1: Put all the nodes in the heap. Comparison in heap nodes is done based on cost. Initially cost of all the nodes is infinity and cost of source is 0.

Step 2: Extract min node ufrom heap.

Step 3: For all outgoing edges e(u,v, weight) if v.cost > u.cost + e.weight, update the cost of v.

Step 4. if heap not empty repeat step 2.

So in every pass 2–3–4 you will get the source (i.e the minimum element based on cost from the heap) and you will use it to traverse edges and update remaining nodes’ cost in the heap if applied.

Data Structures:

  1. Graph representation -> Adjacency list -> map of node to edge list from nodes. Each edge in the edge list contains the destination node and weight.

2. Routing table -> map of node to struct which maintains its position in the heap, cost of reaching that node and the parent node.

3. Lastly heap.

Cost Analysis:

How many times we iterate = Number of nodes O(V)

Number of nodes in heap -> O(V)

Heap adjust cost in each iteration.

log(O(V)) (After extraction) + O(Ev) log(O(V)) where Ev is the number of edges from vector v.

Thus overall cost.

Sum for all vertex (1+ O(Ev) ) log(O(V).

which is O(V + E) log(O(V)).

Whats next?

See how Prim’s algorithm is very minor change in Dijkstra and thus the cost remains the same.