Blencer - 9 months ago 47

Python Question

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.

Source (Stackoverflow)