stevenbeales
12/27/2018 - 3:01 AM

Dijkstra’s Algorithm

There is an algorithm that computes the shortest distance from a given vertex to the rest of the vertices in a graph. This is called Dijkstra’s Algorithm.

Dijkstra’s Algorithm works like the following:

  • Instantiate a dictionary that will eventually map vertices to their distance from the start vertex
  • Assign the start vertex a distance of 0 in a min heap
  • Assign every other vertex a distance of infinity in a min heap
  • Remove the vertex with the smallest distance from the min heap and set that to the current vertex
  • For the current vertex, consider all of its adjacent vertices and calculate the distance to them as (distance to the current vertex) + (edge weight of current vertex to adjacent vertex).
  • If this new distance is less than the current distance, replace the current distance.
  • Repeat 4 and 5 until the heap is empty
  • After the heap is empty, return the distances

Just like breadth-first search and depth-first search, to search through an entire graph, in the worst case, we would go through all of the edges and all of the vertices resulting in a runtime of O(E + V).

For Dijkstra's, we use a min-heap to keep track of all the distances. Searching through and updating a min-heap with V nodes takes O(log V) because in each layer of the min-heap, we reduce the number of nodes we are looking at by a factor of 2.

In the worst case, we would update the min-heap every iteration. Since there are at most E + V iterations of Dijkstra’s and it takes log V to update a min-heap in the worst case, then the runtime of Dijkstra’s is O((E+V)log V).

In order to keep track of all the distances for Dijkstra's Algorithm, we use heap. Using a heap will allow removing the minimum from the heap to be efficient. In Python, there is a library called heapq which does this.

The heapq method has two critical methods we will use in Dijkstra's Algorithm: heappush and heappop.

  • heappush will add a value to the heap and adjust the heap accordingly
  • heappop will remove and return the smallest value from the heap
.py
content_copyfile_download
# Add values to a heap and remove the smallest value in a heap
import heapq

heap = [(0, 'A')]
heapq.heapush(heap, (1, 'B'))
heapq.heapush(heap, (-4, 'C'))
value, letter  = heapq.heappop(heap)

# Implementation of Dijkstra's algorithm
from heapq import heappop, heappush
from math import inf

graph = {
        'A': [('B', 10), ('C', 3)],
        'C': [('D', 2)],
        'D': [('E', 10)],
        'E': [('A', 7)],
        'B': [('C', 3), ('D', 2)]
    }


def dijkstras(graph, start):
  distances = {}
  
  for vertex in graph:
    distances[vertex] = inf
    
  distances[start] = 0
  vertices_to_explore = [(0, start)]
  
  while vertices_to_explore:
    current_distance, current_vertex = heappop(vertices_to_explore)
    
    for neighbor, edge_weight in graph[current_vertex]:
      new_distance = current_distance + edge_weight
      
      if new_distance < distances[neighbor]:
        distances[neighbor] = new_distance
        heappush(vertices_to_explore, (new_distance, neighbor))
        
  return distances
        
distances_from_d = dijkstras(graph, 'D')
print("\n\nShortest Distances: {0}".format(distances_from_d))