Dijkstra algorithm is commonly used to find most cheapest (optimum) solution to a given problem. In terms of distances, it refers to the shortest distance used to reach destination. This post implements Dijkstra algorithm in Python. A better variant of it, called A-star algorithm is more often used in pathfinding when making games than Dijkstra’s algorithm.

Dijkstra Algorithm in Nutshell

Dijkstra’s algorithm simply takes a graph in its input, travels through its edges, and tries to find the shortest possible distance from source point to destination point. We use it (or its variants) to find the shortest distance from enemy to player characters in video game, or we can use it in applications such as maps to find better route.

In nutshell, this algorithm starts at a source node & checks all unvisited nodes & their neighbors. Whenever it encounters a neighbor, it checks if the distance to it through this current node is more shorter than the previously known distance. If so, update new distance to shorter one, else keep searching until all nodes are eventually set to their most optimum distance from source. After this whole thing, we just usually extract our node of interest, which is destination node.

Understanding Dijkstra’s Algorithm

Looking at the above map, you can easily see that the 150 m path is the shortest, since other roads end up having more meters of distance. But how does Dijkstra’s algorithm figures this out is a bit different. First of all, we need to represent our map in the form of a graph data structure since this computer algorithm takes a graph in its input & returns the shortest path to the destination as its output.

A graph is a structure in which there are points connected through lines. We call points as nodes & lines connecting them as edges. Each edge can have different length. This is not necessarily “length” as it can be any kind of variable here. If you are making a graph of your city’s roads, you can assign the road’s condition & traffic as its weight so the more bigger the value of edge weight, the bad the road’s condition & the more difficult it will be to pass through it. So edge weight can represent any entity. Here we used distance as the edge’s weight (in meters).

In Dijkstra’s algorithm, one thing is very important: the algorithm explores all the paths for every node. So if a particular path that was visited first had a distance of, for example 10 & after a while, it discovered that while passing through a different path, it took distance of 8 to reach there, the algorithm will immediately update the distance to this node. And this happens every time the new smaller distance is found. The fact is, we are interested in the distance to a particular node only, so we simply ignore other distances & only use its value after algorithm has completed its operation.

The Algorithm’s Process:

1. Initially, since it doesn’t know anything, it simply assigns the distance to our starting point (source node) to be equal to zero. And assigns infinity distance to all other nodes! It means that we do not know distances to any other nodes. Also, to keep track of all the visited & unvisited nodes, we need to initialize priority queues (or min-heap). The priority queue is used to store nodes along with their current calculated distances from the source node (at this time, these distance may not be optimal, since later another possible path to the same node can yield a better distance, until algorithm completes).
2. After the stage has been set up in above step, the process begins by getting the node from the “`unvisited_nodes“` that is the neighbor of source node & has the smallest distance from it. The edge with smallest weight will be selected and node connected to it will be taken. We call this nearest-to-source node as “`currentNode“` since we will explore it further. Since we have picked it from “`unvisited_nodes“`, we will now remove it from the “`unvisited_nodes“` queue.
3. Now, in a loop, we will look at each node connected with our currentNode. We call it neighbor. For every neighbor, we check if the distance assigned to it earlier was greater then currently found distance through this currentNode. If it was greater & this one is smaller, we will override the value of this neighbour’s distance to current value (as its smaller, more optimal) & we will also override the “previous_node” to be the current node (since, we will be returning this linked list of nodes as output, with each node connected to previous all the way from source to destination nodes; to keep track of the “path” itself).
4. Process 2 above is a loop iterating over all the nodes from unvisited_nodes queue. And process 3 is the nested loop within currentNode’s loop & iterates over currentNode’s neighbors. After both process have completed, and program successfully exits the loops, we simply return both our path (that was a list) & the distances (to every node, in case we need it).

What happens when previously inefficient path turned out to be more efficient over time than currently selected path?

The main confusion people have about Dijkstra algorithm is that, since it selects the neighbor with least distance to visit next; so it must continues on that path. However, in reality, it does selects the neighbor with least distance, but it still keeps track of other paths as well (which were ignored during the course of algorithm earlier). And once it encounters a case when the current path being followed exceeds in cost to some previously ignored path, it jumps to that path and continues there. Following the order of checking lowest cost neighbor first does not mean sticking to that very path/branch in a graph.

Pseudo-code

function Dijkstra(Graph, source)     
     for each point in Graph.points:
         distance[point] ← INFINITY
         previous_point[point] ← UNDEFINED
         add point to Queue
     distance[source] ← 0
     
     while Queue is not empty:
          currentPoint ← point in Queue with minimum distance[currentPoint]
          remove currentPoint from Queue
   
          for each neighbor of currentPoint still in Queue:
              alt ← distance[currentPoint] + Graph.edges(currentPoint, neighbor)
              if alt < distance[neighbor]:
                  distance[neighbor] ← alt
                  previous_point[neighbor] ← currentPoint

      return distance[], previous_point[]

Python Implementation

import heapq

def dijkstra(graph, start):
    # Initialize distances and visited set
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    visited = set()

    # Priority queue to keep track of the next vertex to visit
    priority_queue = [(0, start)]

    while priority_queue:
        # Get the vertex with the smallest distance
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Skip if the vertex has already been visited
        if current_vertex in visited:
            continue

        # Mark the vertex as visited
        visited.add(current_vertex)

        # Update distances for neighboring vertices
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

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

    return distances

# Example usage
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}
}

start_vertex = 'A'
result = dijkstra(graph, start_vertex)

print(f"Shortest distances from {start_vertex}: {result}")

More

1. https://www.cs.yale.edu/homes/lans/readings/routing/dijkstra-routing-1959.pdf, Dijkstra (1959)