“Dijkstra’s algorithm turns networks into maps — and complexity into clarity”

What is Dijkstra's Algorithm?

Definition:

Dijkstra's Algorithm is a method used to find the shortest path from one point or node (called a source) to all other points in a graph.

We can understand this with the help of simple example suppose You want to go from your home to your friend's house, and there are many roads and intersections. Dijkstra’s Algorithm helps you find the quickest route (shortest distance or time).

Why Do We Use This Algorithm?

We use this algorithm when we need to know the shortest or most efficient path between two things like locations on a map, computers in a network, or steps in a process.

It is useful when:

There are many paths for selection , and we want the best one .
When we think about the time, cost and efficiency.

Advantages of Dijkstra’s Algorithm
Efficient: Finds the shortest path fast and effectively .
Reliable: Always gives the correct shortest path.
Works for all kinds of graphs having positive values.
Simple to understand and apply on positive-weight graphs.
It works on many problems like Great for roads, networks, maps, etc.

Disadvantages of Dijkstra’s Algorithm

1. No Negative Weights:

Dijkstra’s Algorithm can’t handle negative distances.
If a path has a negative cost, the algorithm may give incorrect results.

2. Slow on Large Graphs:

It becomes slow when dealing with many nodes and connections.
Without optimizations, it may take too long to find the shortest path in big graphs.

3. High Memory Usage:

It needs to store all distances and paths.
This can use a lot of memory in large or complex graphs.

4. No Path Reuse:

It recalculates paths every time.
Even if the graph hasn’t changed, it doesn’t remember previous results.

Real Life Applications of Dijkstra’s Algorithm

Here are some common uses of Dijkstra’s Algorithm:

Navigation Systems (e.g. Google Maps):
To find the shortest route from your location to a destination.
Computer Networks:
To find the best path for data to travel between servers or devices.
Artificial Intelligence in Games:
For characters to move in the shortest path across a game map.
Robotics:
For planning the most efficient movement through a space.
Social Media:
Finding the shortest connection between two users.

Lets explain this concept through an example ,

EXAMPLE:

Simple Code in Python Language :

OUTPUT:

The pieces of code with explanation.

import heapq  
def dijkstra(graph, start):   


    distances = {node: float('inf') for node in graph} 
    distances[start] = 0  
    queue = [(0, start)]

The heapq module is used to create a priority queue that always gives the smallest value first.Queue is the mini heap that store the data .

The dijkstra function starts by taking a graph and a starting point. All node distances are set to infinity at first, except for the starting node, which is set to 0. A queue is then created to keep track of which places to visit next, based on the shortest known distance.

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


       if current_distance > distances[current_node]:  
            continue

      for neighbor, weight in graph[current_node]:  

            distance = current_distance + weight   

      if distance < distances[neighbor]:     
           distances[neighbor] = distance    

        heapq.heappush(queue, (distance, neighbor))    

return distances

The loop keeps running until the queue is empty.

It picks the node with the smallest distance and checks its neighbors. If a shorter path is found to any neighbor, the distance is updated and the neighbor is added back to the queue. This helps find the shortest path step by step.

graph = {
    'A': [('B', 1), ('C', 4)],  
    'B': [('A', 1), ('C', 2), ('D', 5)], 
    'C': [('A', 4), ('B', 2), ('D', 1)], 
    'D': [('B', 5), ('C', 1)]  
}
print(dijkstra(graph, 'A'))

Node 'A' has two neighbors:
- 'B' with a distance of 1.
- 'C' with a distance of 4.
  Thus, the distance from A to B is 1, and the distance from A to C is 4.
Node 'B' has three neighbors:
- 'A' with a distance of 1.
- 'C' with a distance of 2.
- 'D' with a distance of 5.
  Therefore, the distances from B are 1 to A, 2 to C, and 5 to D.
Node 'C' has three neighbors:
- 'A' with a distance of 4.
- 'B' with a distance of 2.
- 'D' with a distance of 1.
  Hence, the distances from C are 4 to A, 2 to B, and 1 to D.
Node 'D' has two neighbors:
- 'B' with a distance of 5.
- 'C' with a distance of 1.
  So, the distances from D are 5 to B and 1 to C.

The code then use the concept of the Dijkstra's algorithm, starting from node 'B', to find the shortest paths to all other nodes in the graph. The result then showing the shortest paths in the graph .

IMPORTANT TERMS IN DIJKSTRA’S ALGORITHM:

Node (Vertex): A point in the graph; it represents a location or object (e.g., city, computer).
Edge: A line connecting two nodes; it represents a path or connection.
Weight (Cost): A number assigned to an edge; it shows the distance, time, or cost between two nodes.
Graph: A group of nodes connected by edges; it represents the whole network.
Start Node (Source): The node where the path-finding begins.
Visited Node: A node whose shortest path from the start has already been finalized.
Priority Queue (Min-Heap): A special queue that always gives the next node with the smallest known distance.
Shortest Path: The minimum cost route from the start node to a destination node.

THANK YOU!

Topic : Dijkstra's Algorithm