Dijkstra’s Algorithm Visualizer

— the mother of all path finding algorithm

What is Dijkstra’s Algorithm?

First of all let’s figure out what is Dijkstra’s Algorithm.Yeah the name sounds very weird. It is an path finding algorithm in a graph data structure. Confused of what a graph exactly is ? Graph is a data structure that stores the relation between two nodes (node can be anything that holds a data) for example: Consider Facebook — you can have as many friends and your friend can have the same. Ever thought hoe Facebook store the connection between the users — yes they use Graph Data Structure

How Does it Works?

Now let’s discuss how does the Algorithm works. Consider a graph with weighted edges (the line that connects two nodes is an edge) as shown below

Graph example

Let’s say you are at position 0 and you want to go to position 4. You can easily trace the shortest path to go from position 0 to position 4. But Computers are like child we need to feed them everything. Let’s plot a table to understand the steps involved in the algorithm.

table 1

Considering the 0th position as the starting node we make the distance as 0 (of course the distance from x to x is always gonna be zero). For the case of algorithm we make all other distances as infinity.

Now we want to choose a neighboring nodes of the current node (node 0). The order is not a matter.

currentNode = 0, consideringNode = 1

dist(consideringNode) = dist(currentNode) + weight

here weight is the number on the edge between the current node and the consideringNode. After calculating the distance of the node considered, if the distance is lesser than the existing distance in the table for that particular node, then we replace the value (this is the reason why we use infinity as default distance so that any distance at first will be lesser than infinity). Now consider the second neighbor of the currentNode and do the same.

(note: we need to store the visited node somewhere so that we don’t iterate over the same node which was already visited)

After updating the values of the distance of every neighbors of the current node, add the current node as the from column for all the neighboring nodes. After the traversal of first node the table should look like this:

table 2

Consider the nodes which are not yet visited and pick the node which as the shortest distance in the table. In this example, node 1 has the lowest distance among all the non visited nodes (note that the node 0 is visited). So picking that one up and do the same process until there is no non visited node in the graph. Now the table will be like this one:

table 3

Thus the algorithm, yes you read that right. That’s all for the algorithm. You can use this table to find any shortest distance from node 0 to any other node. For example: let’s say we need to visit the node 4 from node 0, to find the shortest path, we need to backtrack from the node 4. Refer the row of which the node 4 lies. It comes from 5, now look at 5 it comes from 6, repeat that until you get to node 0 (the source). Thus the path will be:

4 -> 5 -> 6 -> 7 -> 0

Visualization:

We are going to use python game module pygame to visualize the algorithm. My implementation was just a practice and contains some bugs but for just visualization that’s okay. I am not going to go through the basics of python. If you don’t know python stop reading it from here.

Create a directory (feel free to name it anything) and create a file named main.py inside the directory and insert the following code in it:

import pygame
from constants import *
from components import *
from helper import *
from algorithm import find_shortest_path
pygame.init()
pygame.display.set_caption("Dijkstra's Algorithm")
screen = pygame.display.set_mode([ WIDTH, WIDTH ])
screen.fill(BLACK)
def main():
 running = True
 dragging = False
 disabled = False
board = Board(screen)
 grid = board.grid
while running:
  board.draw()
for event in pygame.event.get():
   if event.type == pygame.QUIT:
    running = False
if disabled and (event.type == pygame.KEYDOWN or event.type == pygame.MOUSEBUTTONDOWN):
    disabled = False
    board = Board(screen)
    grid = board.grid
elif event.type == pygame.MOUSEBUTTONDOWN:
    if event.button == 1:
     dragging = True
     handle_mouse_event(board)
elif event.type == pygame.MOUSEMOTION and dragging:
    handle_mouse_event(board)
elif event.type == pygame.MOUSEBUTTONUP:
    dragging = False
elif event.type == pygame.KEYDOWN:
    if event.key == pygame.K_SPACE:
     find_shortest_path(board)
     board.start.set_start()
     board.end.set_end()
     disabled = True
pygame.quit()
if __name__ == '__main__':
 main()

now create another file named components.py and paste the follow:

import pygame
from constants import *
from helper import *
class Item():
 ITEM_WIDTH = WIDTH // ROWS
def __init__(self, screen, row, col):
  self.screen = screen
  self.row = row
  self.col = col
  self.color = WHITE
  self.neighbours = []
self.x = self.row * self.ITEM_WIDTH
  self.y = self.col * self.ITEM_WIDTH
def set_start(self):
  self.color = GREEN
def set_end(self):
  self.color = RED
def set_wall(self):
  self.color = BLACK
def set_visited(self):
  self.color = BLUE
def set_path(self):
  self.color = GREY
def get_neighbours(self, grid):
  neighbours = []
if self.row > 0 and grid[self.row - 1][self.col].color != BLACK:
   neighbours.append(grid[self.row - 1][self.col])
if self.row < ROWS - 1 and grid[self.row + 1][self.col].color != BLACK:
   neighbours.append(grid[self.row + 1][self.col])
if self.col > 0 and grid[self.row][self.col - 1].color != BLACK:
   neighbours.append(grid[self.row][self.col - 1])
if self.col < ROWS - 1 and grid[self.row][self.col + 1].color != BLACK:
   neighbours.append(grid[self.row][self.col + 1])
return neighbours
def draw(self):
  pygame.draw.rect(
   self.screen, 
   self.color, 
   (self.x, self.y, self.ITEM_WIDTH, self.ITEM_WIDTH)
  )
def get_pos(self):
  return self.x, self.y
def __str__(self):
  return f"{self.row}, {self.col}"
class Board():
 def __init__(self, screen):
  self.screen = screen
  self.grid = generate_grid(screen, ROWS, ROWS, Item)
  self.start = None
  self.end = None
def _draw_lines(self):
  for row in self.grid:
   for col in row:
    x, y = col.get_pos()
    pygame.draw.rect(
     self.screen, 
     BLACK, 
     pygame.Rect(x, y, col.ITEM_WIDTH, col.ITEM_WIDTH),
     1
    )
  pygame.display.flip()
def draw(self):
  for row in self.grid:
   for col in row:
    col.draw()
    
  self._draw_lines()
  pygame.display.update()

now the constants file:

WIDTH = 800
ROWS = 40
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
BLUE = (0, 0, 255)
GREY = (66, 66, 66)

you can play around with the WIDTH and ROWS to change the UI of the game. make sure that the ROWS is a factor of WIDTH.

make the helper.py file as below

import pygame
from constants import *
def generate_grid(screen, rows, cols, Item):
 grid = []
 for row in range(rows):
  grid.append([])
  for col in range(cols):
   grid[row].append(Item(screen, row, col))
return grid
def get_pos(x, y):
 return x // (WIDTH // ROWS), y // (WIDTH // ROWS)
def handle_mouse_event(board):
 grid = board.grid
 start = board.start
 end = board.end
x, y = pygame.mouse.get_pos()
 row, col = get_pos(x, y)
if not start:
  grid[row][col].set_start()
  board.start = grid[row][col]
elif not end and grid[row][col] != start:
  grid[row][col].set_end()
  board.end = grid[row][col]
elif grid[row][col] != start and grid[row][col] != end:
  grid[row][col].set_wall()

all these files are for the game. Now comes the important part, yes the algorithm implementation, it comes as follows:

def get_min_distance(distance, unvisited):
 minimum = next(iter(distance))
for item in distance:
  if distance[item] < distance[minimum] and not unvisited[item]:
   minimum = item
return minimum
def draw_path(from_list, start, end):
 if end == start:
  return
 end.set_path()
 draw_path(from_list, start, from_list[end])
def find_shortest_path(board):
 grid = board.grid
 start = board.start
 end = board.end
unvisited = {col: False for row in grid for col in row}
distance = {col: float("inf") for row in grid for col in row}
 distance[start] = 0
from_list = {}
while any(unvisited):
  current = get_min_distance(distance, unvisited)
if current == end:
   draw_path(from_list, start, end)
   return True
for neighbour in current.get_neighbours(grid):
   temp_dist = distance[current] + 1
   if temp_dist < distance[neighbour]:
    distance[neighbour] = temp_dist
   
    from_list[neighbour] = current
current.set_visited()
  unvisited[current] = True
return False

I recommend you to code the algorithm by yourself, please don’t just copy paste the code I have made (It has several bugs, I just made it for fun).

For reference here’s the REPO Link

Thanks for Reading