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>My initial approach would be to use some basic backtracking:</p>

<pre class="lang-java prettyprint-override"><code>boolean[][][] visited = new boolean[h][w][d];
boolean foundPath = false;
public void path(int y, int x,int z) {
        visited[y][x][z] = true;
        if (x == targetx &amp;&amp; y == target &amp;&amp; z == targetz) {
            foundPath = true;
            return;
        }
        if (!visited[y - 1][x][z] &amp;&amp; !foundPath) //if up
            path(y - 1, x, z);
        if (!visited[y + 1][x][z] &amp;&amp; !foundPath) //if down
            path(y + 1, x, z);
        if (!visited[y][x - 1][z] &amp;&amp; !foundPath) //if left
            path(y, x - 1, z);
        if (!visited[y][x + 1][z] &amp;&amp; !foundPath) //if right
            path(y, x + 1, z);
        if (!visited[y][x][z+1] &amp;&amp; !foundPath) //if forward
            path(y, x, z + 1);
        if (!visited[y][x][z-1] &amp;&amp; !foundPath) //if backward
            path(y, x + 1, z - 1);

        if (foundPath) return;
        visited[y][x][z] = false;
    }
</code></pre>

python algorithm 3d dijkstra maze