# Ford-Fulkerson Transport Problem Algorithm

By Yori Zwols
on July 6, 2002

Version: 1.00

Type: Function

Category: Algorithms

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 <[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);
}

?>```
﻿