public class PebbleDistanceMatrix
extends java.lang.Object
A non-deterministic algorithm than sometimes returns SOLVABLE very quickly, and other times returns UNKNOWN. It uses
a modification of flyod's algorithm that reduces the reported path lengths when vertices have at least one pebble.
The idea is that when trying to move a pebble along a shortest path what matters is not the actual shortest path, but
the shortest path where there are no pebbles. That doesn't make much sense. Put another way, if there is a path of
1s, then I can move along that path "for free", so that is potentially a shorter path. The bottom line is that this
works better than just floyd's algorithm.
- Author:
- Cusack, 6/29/16