Published in

Analytics Vidhya

# 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

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.

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:

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:

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 pygamefrom constants import *from components import *from helper import *from algorithm import find_shortest_pathpygame.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 = Falseboard = Board(screen) grid = board.gridwhile running:  board.draw()for event in pygame.event.get():   if event.type == pygame.QUIT:    running = Falseif disabled and (event.type == pygame.KEYDOWN or event.type == pygame.MOUSEBUTTONDOWN):    disabled = False    board = Board(screen)    grid = board.gridelif 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 = Falseelif event.type == pygame.KEYDOWN:    if event.key == pygame.K_SPACE:     find_shortest_path(board)     board.start.set_start()     board.end.set_end()     disabled = Truepygame.quit()if __name__ == '__main__': main()`

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

`import pygamefrom constants import *from helper import *class Item(): ITEM_WIDTH = WIDTH // ROWSdef __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_WIDTHdef set_start(self):  self.color = GREENdef set_end(self):  self.color = REDdef set_wall(self):  self.color = BLACKdef set_visited(self):  self.color = BLUEdef set_path(self):  self.color = GREYdef 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 neighboursdef 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.ydef __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 = Nonedef _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 = 800ROWS = 40BLACK = (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 pygamefrom 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 griddef get_pos(x, y): return x // (WIDTH // ROWS), y // (WIDTH // ROWS)def handle_mouse_event(board): grid = board.grid start = board.start end = board.endx, 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 = itemreturn minimumdef 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.endunvisited = {col: False for row in grid for col in row}distance = {col: float("inf") for row in grid for col in row} distance[start] = 0from_list = {}while any(unvisited):  current = get_min_distance(distance, unvisited)if current == end:   draw_path(from_list, start, end)   return Truefor neighbour in current.get_neighbours(grid):   temp_dist = distance[current] + 1   if temp_dist < distance[neighbour]:    distance[neighbour] = temp_dist       from_list[neighbour] = currentcurrent.set_visited()  unvisited[current] = Truereturn 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