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!';
                }
            }
        }
    }
}

?>

Implementation Of Levenshtein Distance Algorithm in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Levenshtein Distance Algorithm (Edit Distance) in PHP
 * @Date : 04-May-2013
 *
 */

$s1 = "POLYNOMIAL";
$s2 = "EXPONENTIAL";

LevenshteinDistance($s1, $s2);


function LevenshteinDistance($s, $t) {
    $m = strlen($s);
    $n = strlen($t);

    for ($i = 0; $i <= $m; $i++)
        $d[$i][0] = $i;
    for ($j = 0; $j <= $n; $j++)
        $d[0][$j] = $j;

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {

            $c = ($s[$i - 1] == $t[$j - 1]) ? 0 : 1;
            $d[$i][$j] = min($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $c);
        }
    }

    printMatrix($d, $s, $t);

    return $d[$m][$n];
}

function flip_row_col_array($array) {
    $out = array();
    foreach ($array as $rowkey => $row) {
        foreach ($row as $colkey => $col) {
            $out[$colkey][$rowkey] = $col;
        }
    }
    return $out;
}

function printMatrix($d, $str1, $str2) {

    $array = flip_row_col_array($d);
    echo "<table border = '1'>";
    echo "<tr>";
    echo "<td>";
    echo "</td>";
    echo "<td colspan=11>";
    echo $str1;
    echo "</td>";
    echo "</tr>";

    $str2 = str_split($str2);

    $count = 0;

    foreach ($array as $j => $value) {

        echo "<tr>";

        foreach ($value as $i => $node) {

            if ($i == 0):

                if ($count == 0):
                    echo "<td>";
                    echo "</td>";
                else:
                    echo "<td>";
                    echo $str2[$j - 1];
                    echo "</td>";

                endif;
                $count++;
            endif;

            echo "<td>";
            echo $node;
            echo "</td>";
        }
        echo "</tr>";
    }
    echo "</table>";
}

?>

Implementation Of Breadth First Search in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Breadth First Search in PHP
 * @Date : 04-May-2013
 *
 */


$g = array(
    0 => array(0, 1, 1, 0, 0, 0),
    1 => array(1, 0, 0, 1, 0, 0),
    2 => array(1, 0, 0, 1, 0, 0),
    3 => array(0, 1, 1, 0, 1, 0),
    4 => array(0, 0, 0, 1, 0, 1),
    5 => array(0, 0, 0, 0, 1, 0),
);

function init(&$visited, &$graph) {
    foreach ($graph as $key => $vertex) {
        $visited[$key] = 0;
    }
}

function breadth_first(&$graph, $start, $visited) {
    // create an empty queue
    $q = array();

    // initially enqueue only the starting vertex
    array_push($q, $start);
    $visited[$start] = 1;
    echo $start . "\n";


    while (count($q)) {
        $t = array_shift($q);
       
        foreach ($graph[$t] as $key => $vertex) {
            if (!$visited[$key] && $vertex == 1) {
                $visited[$key] = 1;
                array_push($q, $key);              
                echo $key . "\t";
            }
        }
        echo "\n";
    }
}

$visited = array();
init($visited, $g);

breadth_first($g, 2, $visited);
?>

Implementation Of Depth First Search in PHP

<?php

/*
 *
 * @Author: Zuhair Mirza
 * @Implementation Of Depth First Search in PHP
 * @Date : 04-May-2013
 *
 */


class Graph {

    protected $_len = 0;
    protected $_g = array();
    protected $_visited = array();

    public function __construct() {
        $this->_g = array(
            array(0, 1, 1, 0, 0, 0),
            array(1, 0, 0, 1, 0, 0),
            array(1, 0, 0, 1, 1, 1),
            array(0, 1, 1, 0, 1, 0),
            array(0, 0, 1, 1, 0, 1),
            array(0, 0, 1, 0, 1, 0),
        );

        $this->_len = count($this->_g);

        $this->_initVisited();
    }

    protected function _initVisited() {
        for ($i = 0; $i < $this->_len; $i++) {
            $this->_visited[$i] = 0;
        }
    }

    public function depthFirst($vertex) {
        $this->_visited[$vertex] = 1;

        echo $vertex . "\n";

        for ($i = 0; $i < $this->_len; $i++) {

            //d(0,$vertex,$this->_g[$vertex][$i],$i);
            if ($this->_g[$vertex][$i] == 1 && !$this->_visited[$i]) {
                $this->depthFirst($i);
            }
        }
    }

}

$g = new Graph();
// 2 0 1 3 4 5
//$g->depthFirst(2);
//$g->depthFirst(0);
$g->depthFirst(2);
?>

Monkey Minimum Number of Jumps Algorithm

<?php

/*
 *
 * Subject : Design & Analysis of Algorithms
 *
 * Question :
 *
  Billo is a monkey trained by our beloved Raju. Billo can perform jumping very eccentrically.
  Given an array of positive integers in which each element represents number of possible hop
  choices that he can jump. Starting with array index=0, design an algorithm that finds the
  minimum number of jumps to reach the end of the array.
  Example:
  Input: A[] = {1, 3, 5, 8, 4, 2, 6, 7, 6, 8, 9}
  Output: 3
  Initially Billo is sitting at index 0. As A[0]=1, he can jump at most 1 hop, i.e., to index 1. At
  index 1, A[1]=3, so he can jump at most 3 hops (to index 2, 3 or 4). Optimally, he can reach
  last position of A in 3 jumps (0 -> 1 -> 3-> 10).
 *
 * @Author: Zuhair Mirza
 * @Date : 4-May-2014
 *
 */

$array = array(1, 3, 5, 8, 4, 2, 6, 7, 6, 8, 9);
//$array = array(1, 4, 3, 8, 5, 6, 2, 9, 7, 8);
//$array = array(1, 4, 3, 2, 5, 6, 2, 9, 7, 8, 9, 8);

$nodeIndex = 0;
$nodeValue = $array[$nodeIndex] + $nodeIndex;

echo $nodeIndex . "->";
$maxKey = runAlgo($array, $nodeIndex, $nodeValue);

function runAlgo($array, $start, $node) {

    for ($j = $start; $j <= $node; $j++) {
        if (isset($array[$j])):
            $newArray[$j] = $array[$j];
        endif;
    }

    if (end($newArray) >= end($array)):

        $maxsIndex = count($array) - 1;
        echo $maxsIndex;
        exit();

    else:

        $maxsIndex = array_keys($newArray, max($newArray));
        echo $maxsIndex[0] . "->";
        $nodeIndex = $maxsIndex[0];
        $nodeValue = $array[$nodeIndex] + $maxsIndex[0];
        $maxKey3 = runAlgo($array, $nodeIndex, $nodeValue);

    endif;

?>