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>Do you know about A* search ("A-star")? It's a modification of Dijkstra's algorithm that can help a great deal when you know something about the geometry of the situation. Unmodified Dijkstra's assumes that any edge could be the start of an astonishingly short path to the goal, but often the geometry of the situation doesn't allow that, or at least makes it unlikely.</p>

<p>The basic idea is that if you are trying to find a shortest path from Denver to Pittsburgh, an edge leading to Salt Lake is not likely to be helpful. So you bias the weights on the heap by adding to them a lower bound on the distance from that node to the goal -- in this 2D case, that would be the straight-line or great-circle distance, since no actual road can be shorter than that. That heuristic tends to push bad choices down further in the heap, so they usually they never get explored.</p>

<p>I can't prove, though, that your way of constructing 3D mazes makes A* search applicable.</p>

python algorithm 3d dijkstra maze