Snippets Algorithms
Algorithms
Ford-Fulkerson Transport Problem Algorithm
by: Yori Zwols
|
July 6, 2002
Version: 1.00
Type: Function
Category: Algorithms
License: GNU General Public License
Description: This is a PHP implementation of the Ford-Fulkerson algorithm for solving the standard linear programming transport problem.
<?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 <yori@1stsign.net>
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);
}
?>
PHPBuilder
Policies
PHP Developer
Topics
PHP Developer
Resources
PHP Developer
References
