Implementation Of Bellman Ford Algorithm in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Bellman Ford Algorithm in PHP
 * @Date : 01-June-2014
 *
 * The Bellman–Ford algorithm is an algorithm that computes shortest
 * paths from a single source vertex to all of the other vertices in a weighted digraph
 *
 */

define('INFINITY', 10000000);

$matrix = array(
    0 => array(0, 3, 4),
    1 => array(0, 0, 2),
    2 => array(0, -2, 0),
);

$len = count($matrix);

$dist = array();

BellmanFord($matrix, $dist, 0);

// [0, 2, 4]
var_dump($dist);

function BellmanFord(&$matrix, &$dist, $start) {
    global $len;

    foreach (array_keys($matrix) as $vertex) {
        $dist[$vertex] = INFINITY;
        if ($vertex == $start) {
            $dist[$vertex] = 0;
        }
    }

    for ($k = 0; $k < $len - 1; $k++) {
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {

                echo $i . "--" . $dist[$i] . "<br/>";
                echo $j . "--" . $dist[$j] . "<br/>";
                echo $matrix[$j][$i] . "<br/>";
                echo "-------------<br/>";

                if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                    $dist[$i] = $dist[$j] + $matrix[$j][$i];
                    echo "------Done-------<br/>";
                }
            }
        }

        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                if ($dist[$i] > $dist[$j] + $matrix[$j][$i]) {
                    echo 'The graph contains a negative cycle!';
                }
            }
        }
    }
}

?>