I am trying to implement the Floyd–Warshall algorithm on a maze to calculate the distance from one point to all of the other points inside the maze. For some reason, when I use a k which equals the maximum between the columns and the rows, I get an incorrect answer.
Is there a way to solve this with a value of k which would be correct for all lengths of a given maze?
In other words, is there a way to use the Floyd-Warshall algorithm for a non-n×n matrix? That is, for a m×n matrix where m != n?
If the maze is of the narrow passage sort (which is quite common and probably the case here) then having a vertex for each cell does not make sense because it would add absolutely unnecessary vertices with the cost to each path being the same (unweighted).
The right way to model your graph is to assign a vertex to each intersection (not corner). I. e. if at any point the choices is between 3 or 4 directions place a vertex. If you can go only forward or backward then do not assign a vertex.
This would yield a fairly compact number of vertices even for a large maze.
Next, the weight of the path between a pair of vertices is simply the number of squares on the solitary direct path between the two vertices. This can be easily computed by going in each of the maximum four directions of the vertex and counting the number of hops.
Thus you start out with vertices and path weights and I am sure Floyd-Warshall will give you shortest path lengths between each pair with no problem.
The matrix will be NxN (and not MxN etc.)
Edit: Additionally, if your maze is not of the "narrow passage" sort and you can usually go in all four directions, then instead of Floyd-Warshall or graph algorithms, use A*-search or simulated annealing or that set of global optimization algorithms. (A*-search is what I would recommend)