- Use dictionary comprehension for init of map - Use pointer to previous node instead of entire path, backtrack if necessary - Use siftdown instead of heapify - Use list of adjacent nodes instead of map - (Use Cython for critical parts)