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 *
for i in range(len(vertices)):
for u in sons(vertices[currentVertex]):
if v in covered:continue
return "No path!"
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.