Floyd–Warshall algorithm on m-by-n matrix [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

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?

Answer 1

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)

Answer 2

No.

You seem to be confused about the purpose of the matrix in Floyd-Warshall algorithm: for two locations i,j in the maze the matrix A[i,j] stores weight of edge i -> j (perhaps infinity, if there is no edge). Both columns and rows indicate locations, it is nonsensical for a nonsquare matrix.

If you have a rectangular maze of size M x N, and all possible places are possible, then you need (M*N) x (M*N) matrix for Floyd-Warshall algorithm. Assuming you can only go in 4 directions this is a real waste of space.

If you want shortest paths from one vertex, use Dijkstra's algorithm, it's much faster. If the edges do not have weight, even better, use plain BFS.

Answer 3

From the Wikipedia article, it would seem that it is possible to use Floyd-Warshall on a non-square matrix. I'm not familiar enough with the details of the algorithm to explain how, but I'll keep looking at it.

Based on what I know of mazes, though, I think a first step would be to generate a graph representing the maze with each non-wall "edge" of a point represented by 1 and each wall represented by either infinity or some very large number.

Answer 4

I don't see a reason for your problem in this algorithm. To my knowledge, that algorithm does not have any limitation in terms of size of the matrix (note: you can use any graph!).

A quick overview at wikipedia confirms my guess.

I can only think that you might have a bug in your implementation or in the definition of the graph. Also, could you have any negative cycles?