top of page

Learn through our Blogs, Get Expert Help, Mentorship & Freelance Support!

Welcome to Colabcodes, where innovation drives technology forward. Explore the latest trends, practical programming tutorials, and in-depth insights across software development, AI, ML, NLP and more. Connect with our experienced freelancers and mentors for personalised guidance and support tailored to your needs.

Coding expert help blog - colabcodes

Dijkstra’s Algorithm with Python Implementation

  • Writer: Samul Black
    Samul Black
  • Aug 19, 2024
  • 4 min read

Updated: Aug 6

Dijkstra’s Algorithm is a classic and fundamental algorithm in computer science used for finding the shortest path from a starting node to all other nodes in a weighted graph. Named after its creator, Edsger W. Dijkstra, the algorithm is widely used in various applications such as network routing, geographical mapping, and optimization problems. In this blog, we’ll explore the core concepts of Dijkstra’s Algorithm, its implementation in Python, and some practical applications.

Dijkstra’s Algorithm colabcodes

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm is a foundational graph traversal algorithm used to compute the shortest path from a single source node to all other nodes in a weighted graph—provided all edge weights are non-negative. It is widely used in routing and navigation systems, such as GPS mapping software, network packet routing, and AI pathfinding in games.

Originally proposed by Dutch computer scientist Edsger W. Dijkstra in 1956, this algorithm laid the groundwork for many modern optimization techniques in graph theory and has become an essential tool in computer science and operations research.


Why Use Dijkstra’s Algorithm?

Dijkstra's Algorithm is especially useful in real-world applications where finding the shortest or most cost-effective route is essential. Examples include:


  1. GPS Navigation: Calculating the shortest driving distance between two locations.

  2. Internet Routing: Finding the least-cost path for data packets across a network.

  3. Project Planning: Determining the quickest path through a series of dependent tasks.

  4. Video Games and Robotics: Guiding characters or agents through obstacle-laden environments.


Key Concepts in Dijkstra’s Algorithm

To fully understand Dijkstra’s Algorithm, it’s important to grasp the following core concepts:


  1. Shortest Path: The smallest total weight (or cost) from the source node to a target node, considering all valid routes.

  2. Priority Queue (Min-Heap): A data structure that efficiently selects the node with the current shortest known distance for processing. This helps the algorithm focus on the most promising paths first.

  3. Distance Vector (Distance Array): An array or mapping that keeps track of the shortest known distance from the source node to every other node. Initially, all distances are set to infinity, except for the source node, which is set to zero.

  4. Visited Set: A collection of nodes that have already been fully processed and won’t be revisited, preventing unnecessary computation.


Dijkstra’s Algorithm: Step-by-Step Breakdown

Here’s a high-level breakdown of how Dijkstra’s Algorithm works:


1. Initialization

Assign a tentative distance value to every node:


  • 0 for the source node.

  • ∞ (infinity) for all other nodes.


Create an empty priority queue (min-heap) and insert the source node with a priority of 0. Initialize a set or boolean array to keep track of visited nodes.


2. Processing Nodes

While the priority queue is not empty:


  1. Extract the node u with the smallest distance from the priority queue.

  2. If u has already been visited, skip it.

  3. For each unvisited neighbor v of node u:


    • Calculate the tentative distance:distance[u] + weight(u, v)

    • If this tentative distance is less than the currently recorded distance for v, update it.

    • Insert or update node v in the priority queue with the new distance.


  4. Mark node u as visited.


3. Termination

The algorithm continues until:


  • All reachable nodes have been visited, or

  • The priority queue becomes empty.


At this point, the distance vector contains the shortest path distances from the source node to all other nodes in the graph.


Python Implementation for Dijkstra’s Algorithm

Let’s implement Dijkstra’s Algorithm in Python using a priority queue for efficient retrieval of the node with the smallest distance.

import heapq

def dijkstra(graph, start):
    # Initialize distances with infinity
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # Distance to source is 0

    # Priority queue to select the node with the smallest distance
    priority_queue = [(0, start)]  # (distance, node)

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

        # Skip if we found a better path already
        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            # If a shorter path to neighbor is found
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances
# Example graph (undirected and weighted)
graph = {
    'A': [('B', 2), ('C', 5)],
    'B': [('A', 2), ('C', 6), ('D', 1)],
    'C': [('A', 5), ('B', 6), ('D', 3), ('E', 8)],
    'D': [('B', 1), ('C', 3), ('E', 4)],
    'E': [('C', 8), ('D', 4)]
}

start_node = 'A'
shortest_distances = dijkstra(graph, start_node)

print(f"Shortest distances from node '{start_node}':")
for node, distance in shortest_distances.items():
    print(f" - {node}: {distance}")

Output:
Shortest distances from node 'A':
 - A: 0
 - B: 2
 - C: 5
 - D: 3
 - E: 7

This implementation of Dijkstra’s Algorithm uses a priority queue (min-heap) to always process the next closest node. The distances dictionary keeps track of the current shortest distance from the start node to every other node. At each step, the algorithm extracts the node with the smallest known distance, checks all its neighbors, and updates their distances if a shorter path is found. If a neighbor's distance is updated, it is pushed into the priority queue so it can be processed later. The process continues until all reachable nodes have been processed. The final result is a dictionary mapping each node to its shortest distance from the source.



Conclusion

Dijkstra’s Algorithm is a fundamental and versatile tool for solving shortest path problems in graphs with non-negative edge weights. Its combination of efficiency, simplicity, and wide applicability makes it a go-to solution in numerous domains—from GPS navigation and internet routing to game development and logistics. By leveraging a greedy approach and efficient data structures like priority queues, it ensures optimal results with minimal computational overhead.

With the Python implementation provided, you're equipped to begin applying Dijkstra’s Algorithm to your own graph-based problems—be it in educational projects, business applications, or real-world systems

As you deepen your understanding, consider exploring variations like A* Search for heuristic-based pathfinding or Bellman-Ford for handling negative weights. Dijkstra’s Algorithm is not just a classic—it’s a critical building block in the toolkit of every programmer, data scientist, and engineer.

Get in touch for customized mentorship, research and freelance solutions tailored to your needs.

bottom of page