When you search for directions on your GPS or plan delivery routes in a logistics application, what happens behind the scenes is often powered by a classic algorithm from 1956—Dijkstra's Algorithm. Designed by the Dutch computer scientist Edsger W. Dijkstra, this algorithm has stood the test of time. It continues to be widely used in many practical applications that involve shortest-path problems.

This post will explore how Dijkstra’s Algorithm works, how to implement it in Python using a custom approach, and where it’s commonly used. This guide will help you understand the logic of the algorithm and walk you through an original Python implementation.

What is Dijkstra's Algorithm?

Dijkstra's Algorithm finds the quickest way to get from a starting node in a weighted graph to all the other nodes. A weighted graph is a collection of nodes connected by edges, where each edge has an associated numeric value, or weight, representing the cost or distance between two nodes.

This algorithm is especially effective when all edge weights are non-negative. It works by continually selecting the node with the smallest known distance from the starting point, updating the distances of its neighbors, and marking it as “visited.” This process continues until all nodes have been processed.

Key Ideas Behind the Algorithm

To fully grasp Dijkstra’s Algorithm, it’s important to understand a few basic concepts that form the foundation of its logic:

• Graph: A collection of points (called nodes) and lines connecting them (called edges). Each edge carries a weight representing the cost or distance.
• Greedy Strategy: Dijkstra’s Algorithm uses a greedy approach, always choosing the next closest unvisited node to explore.
• Priority Mechanism: Nodes are selected based on their current shortest distance from the start node.

The algorithm maintains a list of distances from the start node to every other node in the graph. Initially, all distances are set to infinity, except the starting node, which is set to 0. The algorithm repeatedly picks the node with the smallest known distance, updates the distances to its neighbors, and continues until all nodes have been visited.

How the Algorithm Works (Step-by-Step)

Let’s break the algorithm down into steps:

1. Initialize all distances to infinity, except for the source node, which gets a distance of 0.
2. Mark all nodes as unvisited. The unvisited set contains all the nodes that need to be evaluated.
3. Pick the point that hasn't been visited yet that is closest. It is the current node.
4. For each neighbor of the current node that hasn't been visited yet:
   • Figure out the likely distance through the present node.
   • Change the distance if this new distance is less than the old distance.
5. Mark the current node as visited.
6. Repeat steps 3–5 until all nodes have been visited or the shortest distance to a target node is found.

This process guarantees that once a node is visited, the shortest path to it has been found.

Python Implementation of Dijkstra's Algorithm

Now that you understand the algorithm’s logic, let’s write our implementation in Python. This version avoids using built-in modules like heapq and instead demonstrates the priority mechanism using simple lists to keep it educational and transparent.

Graph Representation

This guide will represent a graph using a dictionary where each key is a node, and its value is another dictionary containing its neighbors and the weights of the edges connecting to them.

# Graph definition using adjacency dictionary

graph = {

'A': {'B': 3, 'C': 1},

'B': {'A': 3, 'C': 7, 'D': 5},

'C': {'A': 1, 'B': 7, 'D': 2},

'D': {'B': 5, 'C': 2}

}

The Dijkstra Function

Now, let’s define the function to compute the shortest paths. It will maintain a dictionary for distances and another to track visited nodes.

def dijkstra_algorithm(graph, start):

# Initialize distances with infinity and set starting point to 0

shortest_distances = {node: float('inf') for node in graph}

shortest_distances[start] = 0

visited_nodes = set()

while len(visited_nodes) < len(graph):

# Find the unvisited node with the smallest distance

current_node = None

for node in graph:

if node not in visited_nodes:

if current_node is None or shortest_distances[node] < shortest_distances[current_node]:

current_node = node

if current_node is None:

break # All remaining nodes are unreachable

# Visit each neighbor and update distances

for neighbor, weight in graph[current_node].items():

if neighbor not in visited_nodes:

new_distance = shortest_distances[current_node] + weight

if new_distance < shortest_distances[neighbor]:

shortest_distances[neighbor] = new_distance

# Mark the current node as visited

visited_nodes.add(current_node)

return shortest_distances

Running the Algorithm

Let’s see the output for our sample graph starting from node 'A'.

start_node = 'A'

distances = dijkstra_algorithm(graph, start_node)

print("Shortest distances from node A:")

for node in distances:

print(f"A -> {node}: {distances[node]}")

Expected Output

Shortest distances from node A:

A -> A: 0

A -> B: 3

A -> C: 1

A -> D: 3

This output tells us that:

• The shortest distance from A to B is 3.
• The shortest distance from A to C is 1.
• The shortest distance from A to D is 3 (A → C → D).

Understanding the Output

This algorithm explores the network by always taking the shortest possible step from the starting point and expanding outwards. In our example, starting from node A, the algorithm quickly identifies that going from A to C to D is a better path than going A → B → D, which would cost more (3 + 5 = 8). It is the power of Dijkstra’s Algorithm—it finds optimal paths without needing to explore every single route.

Conclusion

Dijkstra’s Algorithm is one of the most elegant and practical algorithms in computer science. It solves a common problem—finding the shortest path—using a simple and reliable method. Its applications span across many domains, from routing internet traffic and guiding robots to powering the GPS in your phone. This post will broke down the logic of Dijkstra’s Algorithm, implemented it step-by-step in Python, and examined how it works with a sample graph. Our unique approach to the code ensures clarity and ease of understanding while avoiding the use of external libraries or standard heap structures.