package frink.function;

/** This implements a solver for Floyd's algorithm, also called Floyd-Warshall,
    which finds *all* the shortest distances through a graph between all pairs
    of nodes in a graph.

    It runs in O(n^3) time which might sound theoretically no better than n
    calls to Dijkstra's algorithm (which is O(n^2) and only finds the best
    path between two nodes) but these loops are extremely simple and tight,
    which makes it efficient.  Floyd's algorithm is also much more efficient
    than n calls to Dijkstra's algorithm because of the highly-repeated nature
    of shortest paths through a graph.  However, the algorithm as written only
    finds the *lengths* of the paths between nodes and not the paths
    themselves, which is sometimes all you need, which also makes it much
    faster than an implementation of n calls to Dijkstra's algorithm that also
    finds the paths.

    See The Algorithm Design Manual, Stephen Skiena, section 6.3.2.
    
    This version also eliminates memory allocation of "visited" nodes as in
    Dijkstra's algorithm, and bails out early when nodes are disconnected and
    cannot possibly improve a solution, unlike Skiena's implementation.

    Note that Skiena has some disastrous advice (e.g. initialize disconnected
    edges to MAXINT which would always cause silent numerical overflow or
    wraparound in his algorithm.)  He repeats this in his book and lectures
    and slides and videos.
    https://www3.cs.stonybrook.edu/~skiena/392/newlectures/week10.pdf

    He must have known something was wrong finally because his implementation
    redefines MAXINT as the even-more distastrous random number 100007 LOL
    which, instead of always failing, just sometimes silently fails.  That
    implementation also has strange (and very small) hard-coded limitations on
    the size of graphs which will cause silent array-out-of-bounds errors
    in C.
    
    https://github.com/SkienaBooks/Algorithm-Design-Manual-Programs/blob/ee2317074936a0a275f2dd05e2f9f7c7debf9918/floyd.c

    This version fixes those flaws by defining a specific "disconnectedVal"
    which is the value that notes that nodes are disconnected.  (-1 is
    recommended.)  It also improves on Skiena's implementation by bailing out
    as early as possible when nodes are not connected and cannot possibly
    improve the solution.  This drastically improves runtime for many graphs,
    especially sparsely-connected ones.

    @author Alan Eliasen, eliasen@mindspring.com
*/
public class Floyd
{
   /** Finds all the shortest distances between all of the nodes in a graph
       represented by the adjacency matrix g.

       @param g A square adjacency matrix.  The value g[i][j] is the weight to
       travel from node i to j.  The matrix is modified in-place.

       @param disconnectedVal The value to be treated as "no connection"
       between nodes.
   */
   public static void shortestDistances(int[][] g, int disconnectedVal)
   {
      int i, j;  // Array indices
      int k;
      int through_k; // Distance through vertex k
      int wik;   // Weight between i,k
      int wkj;   // Weight between k,j
      int wij;   // Weight between i,j

      int len = g.length;
      if (g[0].length != len)
      {
         System.err.println("Floyd.shortestDistances:  array is not square!");
         return;
      }

      LOOPK:
      for (k=0; k<len; k++)
      {
         LOOPI:
         for (i=0; i<len; i++)
         {
            wik = g[i][k];
            if (wik == disconnectedVal)
               continue LOOPI;

            LOOPJ:
            for (j=0; j<len; j++)
            {
               wkj = g[k][j];
               if (wkj == disconnectedVal)
                  continue LOOPJ;

               // At this point, wik and wjk are known *not* to be the
               // disconnected value so their sum is valid and won't silently
               // fail as in Skiena.
               through_k = wik + wkj;
               wij = g[i][j];
               if (wij == disconnectedVal || through_k < wij)
                  g[i][j] = through_k;
            }
         }
      }
   }
}