Ford-Fulkerson Transport Problem Algorithm

<?PHP

/* FORD-FULKERSON TRANSPORT PROBLEM SOLVING ALGORITHM

   Based on a Pascal implementation, which can be found in
        "Discrete Optimization Algorithms with Pascal Programs"
        Maciej M. Syslo, Narsingh Deo, and Janusz S. Kowalik.
        1983, Prentice-Hall, Inc., Englewood Cliffs, NJ
        (TRANSPOR.PRC)
        http://www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml

   PHP translation and documentation by Y. Zwols <[email protected]>


   INPUT
   -----
     $m                    Number of supply nodes
     $n                    Number of demand nodes
     A                     Array[0..M-1] of supply quantities
     B                     Array[0..N-1] of demand quantities
     C                     Array[0..M-1, 0..N-1] of costs

   OUTPUT
   ------
     X : ARRSP             Array[0..M-1, 0..N-1] of flow that minimizes 
                           total costs
     KO : Float            Optimal total costs
*/

function Transport($m, $n, $a, $b, $c, &$x, &$ko)
{
   $inf = 10000;
   $steps = 0;

   for ($i=0; $i < $m; $i++) 
     $u[$i] = 0;
   for ($j=0; $j < $n; $j++)
   {
     $r = $inf;
     for ($i=0; $i < $m; $i++)
     {
       $x[$i][$j] = 0;
       $sf = $c[$i][$j];
       if ($sf < $r)
          $r = $sf;
     }
     $v[$j] = $r;
   }
   $lab1 = false;
   do {
      for ($i=0; $i < $m; $i++)
      {
         $w[$i] = -1;
         $eps[$i] = $a[$i];
      }
      for ($j=0; $j < $n; $j++)
      {
         $k[$j] = -1;
         $del[$j] = 0;
      }
      do {
         $lab  = true; 
         $lab2 = true;
         $i    = 0;
         do {
            $sf = $eps[$i];
            $eps[$i] = -$eps[$i];
            if ($sf > 0) 
            {
               $ra = $u[$i];
               $j = 0;
               do {
                   if (($del[$j] == 0) && ($v[$j]-$ra == $c[$i][$j]))
                   {
                      $k[$j] = $i;
                      $del[$j] = $sf;
                      $lab = false;
                      if ($b[$j] > 0)
                      {
                         $lab = true;
                         $lab2= false;
                         $sf = abs($del[$j]);
                         $r = $b[$j];
                         if ($r < $sf)
                            $sf = $r;
                         $b[$j] = $r - $sf;
                         do {
                            $i = $k[$j];
                            $x[$i][$j] += $sf;
                            $j = $w[$i];
                            if ($j != -1) $x[$i][$j] -= $sf;
                         } while ($j != -1);
                         $a[$i] -= $sf;

                         // if b[j] <= 0 for all j, OPTIMAL
                         $j = 0;
                         do {
                            $lab1 = ($b[$j] <= 0);
                            $j++;
                         } while (($j < $n) && ($lab1));
                         if ($lab1)
                         {
                           $ko = 0;
                            for ($i = 0; $i < $m; $i++)
                               for ($j = 0; $j < $n; $j++)
                                  $ko += $x[$i][$j] * $c[$i][$j];
                         }
                      } // if ($b[$j]) 
                   } // if (($del[$j] ...
                   $j++;
               } while (($j < $n) && ($lab2));
            } // if ($sf > 0) ...
            $i++;
         } while (($i < $m) && ($lab2));
         if (!$lab)
         {
            $lab = true;
            for ($j = 0; $j < $n; $j++)
            {
               $sf = $del[$j];
               if ($sf > 0)
               {
                  for ($i = 0; $i < $m; $i++)
                  {
                     if ($eps[$i] == 0)
                     {
                        $r = $x[$i][$j];
                        if ($r > 0)
                        {
                           $w[$i] = $j;
                           if ($r <= $sf) 
                              $eps[$i] = $r;
                           else
                              $eps[$i] = $sf;
                           $lab = false;
                        } // if ($r > 0)
                     } // if ($eps[$i] == 0)
                  } // for ($i ... )
                  $del[$j] = -$sf;
               } // if ($sf > 0)
            } // for ($j ... )
         } // if (!$lab) 
      } while (!$lab);

      if ($lab2)
      {
         $r = $inf;
         for ($i = 0; $i < $m; $i++)
         {
           if ($eps[$i] != 0)
           {
             $ra = $u[$i];
             for ($j = 0; $j < $n; $j++)
             {
                if ($del[$j] == 0) 
                {
                   $sf = $c[$i][$j] + $ra - $v[$j];
                   if ($r > $sf) 
                       $r = $sf;
                } // if ($del[$j])
             } // for ($j ... )
           } // if ($eps[$i] != 0)
         }
         for ($i = 0; $i < $m; $i++) 
           if ($eps[$i] == 0) 
              $u[$i] += $r;
         for ($j = 0; $j < $n; $j++) 
           if ($del[$j] == 0) 
              $v[$j] += $r;
     }
     $steps++;
     if ($steps == 1000) 
        die ("Algorithm has encountered an infinite loop");
   } while (!$lab1);
}

?>