Dijkstra Algorithm

Solution to the single-source-shortest-path problem in graph theory

Problem

Need of algorithm for single source shortest path to solve multiple problems with competitive complexity. Shortest in terms of cost, distance or time.

Examples for single source shortest path problems Flight itineraries, Google Maps, Network Routing, Circuit Wiring, Telephone Network etc.

Dijkstra Algorithm Brute Force Implementation

It is a Single Source Shortest Path Algorithm for graphs. Dijkstra uses greedy approach to find shortest path.

For Implementation we will require Priority Queue and distance array. Priority Queue will have key as node index and value as distance.

Distance will track optimal distance to visit each node index. Initially, all the distance will be marked as positive Infinity and source node’s initial distance marked as 0. Infinity is indication of unreachable node index and Priority Queue will indicate which nodes to choose next based on key value pair. After getting lowest weight we will update the previous weight.

Visualizing the Algorithm

At Starting Source weight is 0 and other weights are initialised as infinity

We have path from A->B and edge weight is 4. so, updated on table and priority-queue

We have path from A->C and edge weight is 1. so, updated on table and priority-queue

We have path from A->C->B and edge weight will be 1+2=3 which is lesser than previous weight. so, updated on table and priority-queue

We have path from A->C->D and edge weight is 1+5=6. so, updated on table and priority-queue

We have path from A->C->B->D and edge weight will be 1+2+1=4 which is lesser than previous weight. so, updated on table and priority-queue

We have path from A->C->B->D->E and edge weight will be 1+2+1+3=7 so, updated on table and priority-queue

Dijkstra Algorithm Source Code

Time and Space Complexity Analysis

We are Simply using D.F.S algorithm to traverse all the edges so, it will take O(V+E) in worst case.

Priority-queue is using heap in implementation so, for building Priority-queue will take O(V) where ‘V’ is total number of nodes in graph, but updating and deleting, it will take O(log V) so, update part of algorithm will take O(V*log(V)) and D.F.S will take O(V+E). So, complexity in worst case will be O(E + V*Log(V)).

Optimization of Dijkstra Algorithm

If you have dense graph and you have applied same algorithm than It will give lot’s of updates then insert. so, we need to optimize update part to optimize overall algorithm. we can optimize it using Indexed Priority-queue or using D-ary heap.

Basically, D-ary heap is variation of heap implementation. Each node is having D children. which speeds up decrease key operations but at same time it will increase cost of removal.

By using D-ary heap our complexity will be reduced from O(E + V*Log(V)) to O(E * log(E/V)(V)) due to balance removals in E/V time.

Limitations / Dis-advantages

It search all the edges blindly, so, takes more time in processing

It can not handle Negative Edge Weights and it end up forming acyclic graph and it will not obtain the shortest possible path.

It will not work when graph’s nodes are not connected.

Real Life Examples of Dijkstra

Routing Protocols of Routers using this algorithm to update forward table(In Routers it is responsible for package forwarding). It gives shortest path between routers.

Google Maps uses Dijkstra Algorithm for finding shortest path between nodes in a graph. For example, if we consider road networks are edges and destination and source are nodes. In easy implementation it takes things in consideration like road is under-construction, road is blocked, rivers, mountain or any other obstacles as a node and path is an edge and by taking this in consideration it may show few shortest paths to reach your destination.

Network Delay Time Question based on Dijkstra (Leetcode 743)

Problem Statement

N network nodes are given, they are labelled as 1 to N. Given times list as directed edges. times[i]=(u,v,w), where u is source node, v is target node and w is time takes to travel from source to target.

Now, we send a signal from a certain node k. return time takes to receive target else return -1.

E.g. 1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Solution of the problem using Dijkstra

Intuition We can easily find min. distance from source to target using Dijkstra Algorithm

Time and Space Complexity

Tree-set Complexity of add, contain and remove will take O(log N) due to internal red-black tree implementation but the elements are sorted and node can be insert in O(1) time.

So, for V elements insert and delete it will take up to O(V*log V) and D.F.S traversal will take O(V+E) so, again complexity will be O(E+V*log(V)).

List of Leetcode Problems that can be solve using Dijkstra

787. Cheapest Flights Within K Stops

126. Word Ladder II

45. Jump Game II

882. Reachable Nodes In Subdivided Graph

847. Shortest Path Visiting All Nodes

778. Swim in Rising Water