Blencer Blencer - 3 months ago 18
Python Question

Speeding up Dijkstra's algorithm to solve a 3D Maze

I'm trying to write a Python script that can solve 3D mazes and I'm doing it using Dijkstra's algorithm with a priority queue(included in the module heapq). Here is my main function code:

from heapq import *
def dijkstra(start,end,vertices,obstacles):
covered=[]
s=vertices.index(s)
currentVertex=s
liveDistances={}
for i in range(len(vertices)):
liveDistances[i]=inf
liveDistances[s]=0
next=[[liveDistances[s],s]]
while next:
np,currentVertex=heappop(next)
covered.append(currentVertex)
for u in sons(vertices[currentVertex]):
v=vertices.index(u)
if v in covered:continue
if 1+liveDistances[currentVertex]<liveDistances[v]:
liveDistances[v]=1+liveDistances[currentVertex]
heappush(next,[liveDistances[v],v])
if liveDistances[vertices.index(e)]!=inf:
return liveDistances[vertices.index(e)]
else:
return "No path!"


So basically it's just Dijkstra's applied to a 3D graph.

The program works well but I'm wondering if it's normal that it solves a 100x100 2D maze in 10 seconds or a 30x30x30 maze in 2 minutes ?
Am I implementing something wrong here ? Or is it just the right execution time ? Can I enhance it ?

The reason I'm seeking an enhancement is because I'm asked to solve the problem (Finding the shortest path in a 3D maze up to 40x40x40) in less than 5 seconds (The time limit).

Answer

I suspect that a lot of time will be spent in these two lines:

v=vertices.index(u)
if v in covered:continue

both of these lines are O(n) operations where n is the number of vertices in your graph.

I suggest you replace the first with a dictionary (that maps from your vertex names to vertex indices), and the second by changing covered from a list to a set.

This should make both operations O(1) and could give you several orders of magnitude speed improvement.