# I have a working Dijkstra algorithm code for solving mazes but I am looking for more performance

This is my implementation of Dijkstra's algorithm. It solves any order square mazes.

from copy import deepcopy
from math import inf
import maze_builderV2 as mb

def dijkstra(maze, order, pos, finalpos):

mazemap = {}

def scan(): # Converts raw map/maze into a suitable datastructure.
for x in range(1, order+1):
for y in range(1, order+1):
mazemap[(x, y)] = {}
t = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
for z in t:
# print(z, z, maze[z][z])
if maze[z][z] == 'X':
pass
else:
mazemap[(x, y)][z] = 1

scan()

unvisited = deepcopy(mazemap)
distances = {}  # Stores shortest possible distance of each node
paths = {}  # Stores last node through which shortest path was acheived for each node

for node in unvisited:  # Initialisation of distance information for each node
if node == pos:
distances[node] = 0  # Starting location...
else:
distances[node] = inf

while unvisited != {}:
curnode = None
for node in unvisited:
if curnode == None:
curnode = node
elif distances[node] < distances[curnode]:
curnode = node
else:
pass

# cannot use unvisited map is it will keep changing in the loop
for childnode, length in mazemap[curnode].items():
if length + distances[curnode] < distances[childnode]:
distances[childnode] = distances[curnode] + length
paths[childnode] = curnode

unvisited.pop(curnode)

def shortestroute(paths, start, end):
shortestpath = []
try:
def rec(start, end):
if end == start:
shortestpath.append(end)
return shortestpath[::-1]
else:
shortestpath.append(end)
return rec(start, paths[end])
return rec(start, end)
except KeyError:
return False

finalpath = shortestroute(paths, pos, finalpos)

if finalpath:
for x in finalpath:
if x == pos or x == finalpos:
pass
else:
maze[x][x] = 'W'
else:
pass


Problem is that it is quite slow, even compared to other implementations I have seen online. Now I could just copy those, but I wrote this from scratch with minimal help online and by just reading descriptions about the algorithm, all for the purpose of learning. So just copying better code would not serve my purpose.

So can someone tell me where and how I can squeeze some more performance out of this?

Note: If there is a need for my custom maze generating code, here it is:

def mazebuilder(maze, order=10, s=(1, 1), e=(10, 10)):
from copy import deepcopy
from random import randint, choice

maze[s][s] = 'S'  # Initializing a start position
maze[e][e] = 'O'  # Initializing a end position

finalpos = e
pos = s

blocks = []
freespaces = [(x, y) for x in range(1, order+1) for y in range(1, order+1)]

def blockbuilder(kind):
param1 = param2 = 0
double = randint(0, 1)
if kind == 0:
param2 = randint(3, 5)
if double:
param1 = 2
else:
param1 = 1
else:
param1 = randint(3, 5)
if double:
param2 = 2
else:
param2 = 1
for a in range(blockstarter, blockstarter+param2):
for b in range(blockstarter, blockstarter+param1):
if (a+1, b) in blocks or (a-1, b) in blocks or (a, b+1) in blocks or (a, b-1) in blocks or (a, b) in blocks or (a+1, b+1) in blocks or (a-1, b+1) in blocks or (a+1, b-1) in blocks or (a-1, b-1) in blocks:
pass
else:
if a > order+1 or b > order+1:
pass
else:
if maze[a][b] == 'X':
blocks.append((a, b))
else:
spaces = [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]
for c in spaces:
if maze[c][c] == 'X':
break
else:
maze[a][b] = 'X'
blocks.append((a, b))

for x in range(1, order+1):
for y in range(1, order+1):
if (x, y) in freespaces:
t = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
i = 0
while i < len(t):
if maze[t[i]][t[i]] == 'X' or (t[i], t[i]) == pos or (t[i], t[i]) == finalpos:
del t[i]
else:
i += 1
if len(t) > 2:
blockstarter = t[randint(0, len(t)-1)]
kind = randint(0, 1) # 0 - vertical, 1 - horizontal
blockbuilder(kind)
else:
pass

b = 0
while b < len(blocks):
block = blocks[b]
t = {'d':(block+2, block), 'u':(block-2, block), 'r':(block, block+2), 'l':(block, block-2)}
rch = choice(['d', 'u', 'r', 'l'])
z = t[rch]
if z > order-2 or z > order-2 or z < 2+2 or z < 2+2: # Decreased chance of having non solvable maze being generated...
pass
else:
if maze[z][z] == 'X':
if randint(0, 1):
set = None
if rch == 'u':
set = (z+1, z)
elif rch == 'd':
set = (z-1, z)
elif rch == 'r':
set = (z, z-1)
elif rch == 'l':
set = (z, z+1)
else:
pass
if maze[set][set] == '_':
# Checks so that no walls that block the entire way are formed
# Makes sure maze is solvable
sets, count = [(set+1, set), (set-1, set), (set, set+1), (set, set-1)], 0
for blyat in sets:
while blyat != 0 and blyat != 0 and blyat != order+1 and blyat != order+1:
ch = [(blyat+1, blyat), (blyat-1, blyat), (blyat, blyat+1), (blyat, blyat-1)]
suka = []
for i in ch:
if ch not in suka:
if maze[i][i] == 'X':
blyat = i
break
else:
pass
suka.append(ch)
else:
pass
else:
blyat = None
if blyat == None:
break
else:
pass
else:
count += 1
if count < 1:
maze[set][set] = 'X'
blocks.append(set)
else:
pass
else:
pass
else:
pass
b += 1


I believe the code is slow because you are using normal Dijkstra, which takes O(V^2) where V is the number of vertices (Here, V would be N*M).

This is because you are searching for the minimum by iterating through all the unvisited elements, which takes O(V) time. Repeat this for V times and it becomes O(V^2).

You can reduce this to O(V * log V) by using a heap, which would increase your code's performance dramatically.

This is a trick most competitive programmers use ;-)

You can refer on how to use the heaps here:
https://courses.cs.washington.edu/courses/cse326/07au/lectures/lect22.pdf

(This one is for graphs, but you can incorporate it for mazes as well)

• Thanks so much! – Prithvidiamond Feb 10 at 19:00