Dijkstra’s Algorithm

Dijkstra’s Algorithm is used to find the shortest path between vertices/nodes of a graph. It was developed by Edsger W. Dijkstra in 1956 and was published 3 years later. When Dijkstra was working as a programmer at the Mathematical Center in Amsterdam in 1956, he was thinking about the shortest path problem to demonstrate the capabilities of a new computer called ARMAC. It works in a similar way to Prim’s greedy algorithm. For a given source vertex in the graph, it finds the shortest path from that source to all the vertices in the given graph. It can also be used to find the shortest paths from a single node to a single destination node, with the algorithm stopping once the shortest path to the destination node has been determined.

This algorithm can be implemented using min-heap.

Algorithm:

· First a min-heap of size V is created where V is the number of vertices in the graph. The vertex number and distance value of each vertex are stored in each node of the min-heap.

· Source vertex is initialized with distance value as 0 and rest all vertex are initialized with distance infinity.

· While min-heap is not empty, the following steps are performed:

a) From Min Heap, extract the vertex with the smallest distance value node. Let u be the extracted vertex.

b) Check if each of u’s adjacent vertex v is in the Min Heap. If v is in the Min Heap and the distance value is greater than the weight of u-v plus the distance value of u, then v’s distance value is updated by the weight of u-v plus the distance value of u, this is known as relaxation.
Relaxation:
if ( d[u] + c(u, v) < d[v] )
d[v] = d[u] + c(u, v)
where,
d[u] is distance of vertex u.
c(u, v) is edge weight from vertex u to v.
d[v] is distance of vertex v.
example:

here, d[u] = 2, c(u, v) = 2, d[v] = INF(infinity).
It satisfies the condition of relaxation.
Hence, d[v] will be updated from INF to 6.

Example:

1. Source vertex 1 is initialized with distance 0 and rest all vertices with distance INF.

2. Vertex 1 is extracted from min-heap and its adjacent vertices are relaxed.

3. Vertex 2 is extracted and it’s adjacent vertices 3 and 4 are relaxed

4. Vertex 3 is extracted and it’s adjacent vertex 5 is relaxed.

5. Vertex 5 is extracted and its adjacent vertices 4 and 6 are relaxed.

6. Vertex 4 is selected and its adjacent vertex 6 is relaxed.

Shortest distance from the source to all vertices in the given graph from the algorithm.

V d[v]

2 3

3 3

4 8

5 6

6 9

Time Complexity:

Using Binary Min Heap: 𝑂 𝑉 + 𝐸 𝑙𝑜𝑔𝑉 = 𝑂(𝐸𝐿𝑜𝑔𝑉)

Using Fibonacci Min Heap: 𝑂[𝐸 + 𝑉𝑙𝑜𝑔𝑉]

Disadvantage:

For graphs with negative weight cycles, Dijkstra’s algorithm may fail. It may give correct results but it doesn’t allow a vertex to be visited more than one time. For negative weight graphs, the Bellman-Ford algorithm is used.