Ghost in a Cell (Best Path)

Hello all! I am trying to implement Agade’s method of path finding(shortest path time with the most nodes) and currently I create a tree of all possible paths from source to target to find the best route. This method gets the job done but isn’t very efficient seeing as the game times out on games that have a lot of nodes! I am curious on what is a better method to implement? =)

As mentioned by others here, Floyd-Warshall is a simple way to find shortest paths from each node to every other. A small modification maximizes the number of nodes too.
This has time complexity O(n^3), what isn’t too big for n<=15 nodes. Also you only have to run that once before the first move.