Speeding up Dijkstra's algorithm to solve a 3D Maze
<p>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:</p>

<pre><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]&lt;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!"
</code></pre>

<p>So basically it's just Dijkstra's applied to a 3D graph.</p>

<p>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 ?</p>

<p>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).</p>

<p>I suspect that a lot of time will be spent in these two lines:</p>

<pre><code>v=vertices.index(u)
if v in covered:continue
</code></pre>

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

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

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

python algorithm 3d dijkstra maze