Home

 › 

Articles

 › 

Dijkstra’s Shortest Path Algorithm Explained, With Examples

Dijkstra's Algorithm

Dijkstra’s Shortest Path Algorithm Explained, With Examples

Dijkstra’s algorithm is just one example of what we call a shortest-path algorithm. In a nutshell, these are algorithms that are used to find the shortest distance (or path) between vertices of a graph.

While the shortest path can be defined in various ways, such as time, cost, or distance, it usually refers to the distance between nodes. If you want to know more about how Dijkstra’s algorithm works and what you can use it for, you’re in the right place.

What Is Dijkstra’s Algorithm?

In simple terms, Dijkstra’s algorithm is a method for finding the shortest path between nodes in a graph. A source node is designated, and then the distance between this node and all other nodes is calculated using the algorithm.

As opposed to some other shortest-path algorithms, Dijkstra’s can only work with non-negative weighted graphs. That is, graphs where each node’s value represents some quantity, such as cost or distance, and all values are positive.

The Algorithm

Before we dive into how to implement Dijkstra’s algorithm using code, let’s run through the steps involved:

  1. First, we initialize an empty priority queue; let’s call this “Q”. This is the most efficient way to use the algorithm, as it ensures that we always select the next closest vertex to the source node.
  2. Since we don’t yet know the distances from each vertex to the source node, we initialize all the vertex distances to infinity.
  3. The distance of the source vertex, or source node, is also set to 0 as this is our starting point.
  4. The source node is then added to the priority queue with a priority of 0.
  5. To begin, the vertex with the smallest distance is removed from the queue. This vertex is called “u,” and neighboring vertices are designated “v.” The distance from the source node to each v through u is calculated, and if the distance is smaller than the current distance to v, the distance is updated.
  6. Once v is calculated, this is inserted into the priority queue with its priority set to be equivalent to its distance from the source vertex. This ensures that vertices with smaller distances are prioritized first, maintaining the efficiency of the algorithm by considering the closest unvisited vertices first.

Functioning of Dijkstra’s Algorithm

dijkstra's algorithm
Vertices A through F.

Now that we’ve covered the basics behind Dijkstra’s algorithm, let’s take a look at how it would work with an example. First, take a graph with nodes arranged as such:

We have vertices A through F, which are connected to each other through various paths. These connections are also known as edges. If we choose A as our starting vertex, all path values for the other nodes are set to infinity, as previously discussed.

We then go to each vertex and update its path length. If the calculated distance to the adjacent node is less than the current distance to this vertex, the distance is updated.

If we set the priority of each vertex equal to its distance from the source, we avoid visiting nodes twice. When visiting an unvisited node, we go for the shortest path length first. This process is repeated until every node has been visited and the distance from the source node is calculated.

Implementation of Dijkstra’s Algorithm Using a Heap

It’s time to implement some code for Dijkstra’s algorithm into Python and see how this works. We’ll begin by using a simple implementation of a priority queue, known as a heap. The code can be represented as follows:

import heapq
import sys

def dijkstra_heap(adj_matrix, source):
   num_vertices = len(adj_matrix)
   distances = [sys.maxsize] * num_vertices
   distances[source] = 0
   visited = [False] * num_vertices
   heap = [(0, source)]

   while heap:
      current_distance, current_vertex = heapq.heappop(heap)
     visited[current_vertex] = True

      for neighbor_vertex in range(num_vertices):
         weight = adj_matrix[current_vertex][neighbor_vertex]
        
        if not visited[neighbor_vertex] and weight != 0:
           distance = current_distance + weight

        if distance < distances[neighbor_vertex]:
            distances[neighbor_vertex] = distance
             heapq.heappush(heap, (distance, neighbor_vertex))

    return distances

adj_matrix = [   [0, 2, 2, 0, 0, 0],
   [2, 0, 2, 0, 0, 0],
   [2, 2, 0, 2, 2, 6],
   [0, 0, 2, 0, 2, 2],
   [0, 0, 2, 2, 0, 2],
   [0, 0, 6, 2, 2, 0]
]

distances = dijkstra_heap(adj_matrix, 0)
print(distances)

Explanation of the Code

Let’s break this code down step-by-step so we can understand what’s going on.

Importing Modules

Firstly, we’re importing the “heapq” and “sys” modules. The first module allows us to use the heap data structure, while the second allows us to use the maximum integer value. This is needed because we’re initializing the vertex distances to infinity.

Defining Dijkstra’s Algorithm

Next, we define “dijkstra_heap” as a function with two arguments — “adj_matrix” and “source”. These are a representation of the graph as an adjacency matrix and the index of the source node, respectively.

Visiting the Nodes

In this block, we’re calculating the number of vertices. Then, we’re initializing the distances from the source vertex to each destination vertex to infinity, as mentioned before. The source node’s distance is also set to zero.

A list is then created, called “visited,” which is initialized to “False.” This means that nodes are initially considered unvisited until we’ve calculated the distance between them and the source. A priority queue, called “heap,” is also created, with the beginning vertex and distance from the source node designated as a tuple.

Updating the Shortest Path Lengths

Next, we have a “while” loop that runs until the queue is empty. The first line takes the vertex from the heap that has the shortest distance from the source vertex, and the second line marks the vertex as visited once this distance is calculated.

We follow this with a “for” loop, which iterates over all neighbors of the vertex we’re currently concerned with. The weight of each edge is retrieved, and whether neighbor nodes have been visited is checked as well as if the weights are non-zero. The distance to the neighbor node is then calculated using the distance from the source to the current node.

We have another “if” statement, which checks if the distance calculated is shorter than the current shortest distance in our “distances” list. If so, the next line updates this value. Finally, the neighbor vertex, as well as its distance from the source, is added to the heap.

Output of Results

After this process finishes, the distances from the source node to all the other nodes in the graph are returned to the console.

The penultimate code block simply represents the graph we’re looking at as an adjacency matrix, where the value in cell {i, j} represents the weight of the edge that connects the two vertices.

The final code simply tells the system to compute the shortest path distances, and then print these to the console.

Implementation of Code

dijkstra's algorithm
The simple implementation of a heap.

As we can see from the screenshot, we receive an output of [0, 2, 2, 4, 4, 6], representing the shortest path distance from source node A to nodes B, C, D, E, and F.

Best and Worst Use Cases of Dijkstra’s Algorithm

Generally speaking, Dijkstra’s algorithm is seen as efficient, although some algorithms may perform better in specialized cases. With that said, let’s look at the time and space complexity of Dijkstra’s algorithm in the best, average and worst case.

Time Complexity of Dijkstra’s Algorithm

CaseTime Complexity
BestO(E* log V), O(E + V log V) or O(1)
AverageO(E + V log V)
WorstO(V2 log V), or O((E + V) log V)

Usually, we have only one complexity for each case. But, with Dijkstra’s algorithm, the situation isn’t as clear-cut. This is because you can implement the algorithm in different ways, mostly through the use of a priority queue.

When using a priority queue, you could use either a binary heap method or a Fibonacci heap method. Generally, the Fibonacci heap leads to more efficient performance, and a better worst-case time complexity of O((E + V) log V), where E is the number of edges and V is the number of vertices.

If you’re not using a priority queue and the graph is dense, the worst-case complexity could be as inefficient as O(V2 log V).

Regarding the average case, the time complexity is a bit more favorable. The average case refers to when a priority queue is used to calculate the minimum distances to each vertex.

The best case, in strict terms, is an unusual one. You probably wouldn’t bother using the algorithm to solve it. This is because the best case would be where the source vertex is the same as the destination vertex. This means that the iteration terminates itself after only one loop.

The complexity is, in fact, identical to the average case. But since the values of both E and V are equal to 1, this is simplified to O(1). If you’re using a heap to implement your algorithm, then the best-case complexity changes to O(E* log V). This is because there will be a maximum of O(E) vertices in your queue.

Space Complexity of Dijkstra’s Algorithm

CaseTime Complexity
BestO(V)
AverageO(V + E)
WorstO(V2)

As with the time complexity, the space complexity of the algorithm depends on your implementation. If you’re using an adjacency list to represent your graph and a Fibonacci heap or regular heap, the complexity is equal to O(V+E). This is because the vertex distance from the source, as well as the edges between the vertices, need to be stored in memory.

However, if you use an adjacency matrix instead, the complexity is reduced to O(V2). This is because you need to store the vertex distances as well as a V * V matrix to represent the edges.

Wrapping Up

To summarize, Dijkstra’s algorithm is one of many algorithms used for calculating the shortest path lengths in a graph and is very useful. While there are many ways to implement the algorithm, using a priority queue of some description is usually your best bet.

Of these methods, using a Fibonacci heap tends to be the most efficient, particularly for large graphs. For smaller graphs, however, a more simple priority queue may be more than sufficient.

Up Next

Frequently Asked Questions

What is Dijkstra's algorithm?

The algorithm is used to calculate the shortest path lengths between nodes on a graph. It’s an iterative method that starts with the shortest distance from the source node, then updates the distance to neighbor nodes as it goes along.

What are the limitations of Dijkstra's algorithm?

The algorithm can’t handle negative weight edges, which will result in incorrect results.

What is the time complexity of Dijkstra's algorithm?

The time complexity depends on if you’re using a priority queue, and how you’re implementing this. In the best case, where only one iteration is needed, the complexity is O(1).

Otherwise, the best case is either O(E* log V) or O(E + V log V), depending on whether you’re using a standard heap or Fibonacci heap.

In either case, the complexities for the average and worst cases are the same. The worst case can be equivalent to O(V2 log V) if you’re not using a priority queue at all.

What is the space complexity of Dijkstra's algorithm?

It depends on the implementation but can be anywhere from O(V2) to O(V + E).

Can you use Dijkstra's algorithm on a graph that has cycles?

Yes, as long as none of the weight edges are negative.

What are the different ways to implement Dijkstra's algorithm?

You can use a priority queue, such as a heap, or a Fibonacci heap. Generally, a Fibonacci heap leads to more efficient results with larger graphs.

What are the alternatives to Dijkstra's algorithm?

Other shortest path algorithms include the A* algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm. A* tends to be faster but requires more memory.

Bellman-Ford and Floyd-Warshall can both handle negative weight edges unlike Dijkstra’s, but both are more inefficient than Dijkstra’s – they have time complexities of O(VE) and O(V3) respectively.

To top