Understanding Dijkstra's Algorithm: A Step-by-Step Guide 🚀

#dsa #algorithms #learning #datascience

Dijkstra's Algorithm is one of the most famous algorithms in computer science and graph theory, used to find the shortest path from a starting node to all other nodes in a weighted graph. In this blog, we will delve deep into the workings of Dijkstra's Algorithm, providing a step-by-step guide with examples and code implementations. 📝

please subscribe to my YouTube channel to support my channel and get more web development tutorials.

What is Dijkstra's Algorithm? 🤔

Dijkstra's Algorithm, named after its creator Edsger W. Dijkstra, is used to solve the shortest path problem for a graph with non-negative edge weights. It finds the shortest path from a source vertex to all other vertices in the graph.

How Does Dijkstra's Algorithm Work? 🛠️

The algorithm works by iteratively selecting the vertex with the smallest known distance from the source and updating the distances of its neighboring vertices. Here’s a step-by-step explanation:

Initialization:
- Set the distance to the source node to zero and to all other nodes to infinity.
- Mark all nodes as unvisited. Create a set of all the unvisited nodes called the unvisited set.
- Set the initial node as the current node.
Visit Neighboring Nodes:
- For the current node, consider all its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has a length of 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. If the neighboring node has already been visited, skip it.
Mark the Current Node as Visited:
- Once all neighbors of the current node have been visited, mark the current node as visited. A visited node will not be checked again.
Select the Next Current Node:
- Select the unvisited node with the smallest tentative distance and set it as the new "current node", then go back to step 2.
Repeat:
- Repeat steps 2-4 until all nodes have been visited. By then, the shortest path to all nodes will have been found.

Example with Visual Illustration 🌟

Consider the graph illustrated below with the following edges and weights:

The edges and their weights are:

A to B: 4
A to C: 5
B to D: 9
B to C: 11
C to E: 3
D to E: 13
D to F: 2
E to F: 6

Let's find the shortest path from A to all other nodes.

Initialization:
- Distance: A=0, B=∞, C=∞, D=∞, E=∞, F=∞
- Unvisited set: {A, B, C, D, E, F}
- Current node: A
Visit Neighbors of A:
- Update distance for B: Distance[B] = 0 + 4 = 4
- Update distance for C: Distance[C] = 0 + 5 = 5
- Distance: A=0, B=4, C=5, D=∞, E=∞, F=∞
Mark A as Visited:
- Unvisited set: {B, C, D, E, F}
Select B as the Next Current Node:
- Current node: B
Visit Neighbors of B:
- Update distance for D: Distance[D] = 4 + 9 = 13
- Update distance for C: Distance[C] = min(5, 4 + 11) = 5
- Distance: A=0, B=4, C=5, D=13, E=∞, F=∞
Mark B as Visited:
- Unvisited set: {C, D, E, F}
Select C as the Next Current Node:
- Current node: C
Visit Neighbors of C:
- Update distance for E: Distance[E] = 5 + 3 = 8
- Distance: A=0, B=4, C=5, D=13, E=8, F=∞
Mark C as Visited:
- Unvisited set: {D, E, F}
Select E as the Next Current Node:
- Current node: E
Visit Neighbors of E:
- Update distance for F: Distance[F] = 8 + 6 = 14
- Distance: A=0, B=4, C=5, D=13, E=8, F=14
Mark E as Visited:
- Unvisited set: {D, F}
Select D as the Next Current Node:
- Current node: D
Visit Neighbors of D:
- Update distance for F: Distance[F] = min(14, 13 + 2) = 15
- Distance: A=0, B=4, C=5, D=13, E=8, F=14
Mark D as Visited:
- Unvisited set: {F}
Select F as the Next Current Node:
- Current node: F
Mark F as Visited:
- Unvisited set: {}

At this point, all nodes have been visited, and the shortest distances from A are:

A to B: 4
A to C: 5
A to D: 13
A to E: 8
A to F: 14

Python Implementation 🐍

Here’s a Python implementation of Dijkstra's Algorithm:

import heapq

def dijkstra(graph, start):
    # Priority queue to store (distance, node)
    priority_queue = [(0, start)]
    # Dictionary to store the shortest path to each node
    shortest_paths = {start: (None, 0)}
    visited = set()

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_node in visited:
            continue

        visited.add(current_node)

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if neighbor not in shortest_paths or distance < shortest_paths[neighbor][1]:
                shortest_paths[neighbor] = (current_node, distance)
                heapq.heappush(priority_queue, (distance, neighbor))

    return shortest_paths

# Define the graph
graph = {
    'A': {'B': 4, 'C': 5},
    'B': {'D': 9, 'C': 11},
    'C': {'E': 3},
    'D': {'E': 13, 'F': 2},
    'E': {'F': 6},
    'F': {}
}

# Compute the shortest paths
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

# Output the shortest paths
for node, (prev, dist) in shortest_paths.items():
    path = []
    current = node
    while current:
        path.append(current)
        current = shortest_paths[current][0]
    path.reverse()
    print(f"Shortest path to {node}: {dist}, Path: {' -> '.join(path)}")

Conclusion 🎉

Dijkstra's Algorithm is a powerful tool for finding the shortest path in a weighted graph. By understanding and implementing this algorithm, you can solve various real-world problems, such as network routing, geographic mapping, and more. With this detailed explanation and example, you should now have a solid grasp of how Dijkstra's Algorithm works and how to apply it in your own projects.

Series Index

Part	Title	Link
1	8 Exciting New JavaScript Concepts You Need to Know	Read
2	Top 7 Tips for Managing State in JavaScript Applications	Read
3	🔒 Essential Node.js Security Best Practices	Read
4	10 Best Practices for Optimizing Angular Performance	Read
5	Top 10 React Performance Optimization Techniques	Read
6	Top 15 JavaScript Projects to Boost Your Portfolio	Read
7	6 Repositories To Master Node.js	Read
8	Best 6 Repositories To Master Next.js	Read
9	Top 5 JavaScript Libraries for Building Interactive UI	Read
10	Top 3 JavaScript Concepts Every Developer Should Know	Read
11	20 Ways to Improve Node.js Performance at Scale	Read
12	Boost Your Node.js App Performance with Compression Middleware	Read
13	Understanding Dijkstra's Algorithm: A Step-by-Step Guide	Read
14	Understanding NPM and NVM: Essential Tools for Node.js Development	Read