Travelling Elephpant problem

gistfile1.php

<?php

class Tep
{
    /**
     * amount of landmarks available
     * @var integer
     */
    protected $lcount = 0;

    /**
     * current shortest route in kilometers
     * @var float
     */
    protected $shortest;

    /**
     * current shortest path
     * @var array
     */
    protected $shortestPath = array();

    /**
     * list of landmarks/locations elePHPant should visit
     * @var array
     */
    protected $locations = array();

    /**
     * loads a list of landmarks from a csv file
     *
     * @param $filename
     * @return Tep
     */
    public function loadLandmarks($filename)
    {
        $file = new SplFileObject($filename);
        $file->setFlags(SplFileObject::READ_CSV | SplFileObject::SKIP_EMPTY);
        foreach ($file as $row) {
            if ($file->key() == 0) {
                continue;
            }

            $this->addLandmark($row[0], $row[1], $row[2]);
        }

        return $this;
    }

    /**
     * manually adds a landmark to the stack
     *
     * @param string $desc - description of landmark
     * @param float  $lat  - latitude coordinate in degrees
     * @param float  $lng  - longitude coordinate in degrees
     * @return Tep
     */
    public function addLandmark($desc, $lat, $lng)
    {
        $this->locations[] = array(
            'des' => $desc,
            'lat' => deg2rad($lat),
            'lng' => deg2rad($lng),
            'dst' => array(),
        );

        $this->lcount++;
        return $this;
    }

    /**
     * returns landmark by id
     *
     * @param integer $id
     * @return array
     */
    public function getLandmark($id)
    {
        if (!isset($this->locations[$id])) {
            throw new Exception('trying to access none existing landmark');
        }

        return $this->locations[$id];
    }

    public function getJourney()
    {
        $this->getDistanceToAll();

        $paths = $this->preparePaths($this->locations);
        $paths = $this->sortNearest($paths);

        $this->findShortestPath($paths);
        return $this->shortestPath;
    }

    protected function preparePaths($paths)
    {
        $last = $this->lcount - 1;
        unset($paths[$last]);
        foreach ($paths as $index => $loc) {
            unset($paths[$index]['dst'][$last]);
        }

        return $paths;
    }

    protected function sortNearest($paths)
    {
        $sorted = array();
        $from = 0;

        do {
            $current = $from;
            $sorted[] = $from;

            $from = key($paths[$from]['dst']);
            unset($paths[$current]);
            foreach ($paths as $index => $loc) {
                if (isset($paths[$index]['dst'][$current])) {
                    unset($paths[$index]['dst'][$current]);
                }
            }
        } while (isset($paths[$from]));

        unset($sorted[0]);
        return $sorted;
    }

    protected function getDistance($flat, $tlat, $flng, $tlng)
    {
        $r = 6371.0; // radius of the earth in kilometers
        return acos(cos($flat) * cos($flng) * cos($tlat) * cos($tlng)
            + cos($flat) * sin($flng) * cos($tlat) * sin($tlng) + sin($flat) * sin($tlat)) * $r;
    }

    protected function getDistanceToAll()
    {
        foreach ($this->locations as $fid => $floc) {
            foreach ($this->locations as $tid => $tloc) {
                if ($fid == $tid) continue;
                $this->locations[$fid]['dst'][$tid] = $this->getDistance(
                    $floc['lat'], $tloc['lat'],
                    $floc['lng'], $tloc['lng']
                );
            }

            asort($this->locations[$fid]['dst']);
        }
    }

    protected function findShortestPath($locations, $temp = array())
    {
        foreach ($locations as $key => $value) {
            $temp2 = $temp;
            $temp2[] = $value;

            $atemp = $locations;
            $d = $this->getPathDistance($temp2);
            if ($d >= $this->shortest && $this->shortest !== null) {
                break;
            }

            $atemp = $locations;
            unset($atemp[$key]);
            if ($atemp) {
                $this->findShortestPath($atemp, $temp2);
            } else {
                $distance = $this->getPathDistance($temp2);
                if ($distance < $this->shortest || $this->shortest === null) {
                    $this->shortest = $distance;
                    $this->shortestPath = $temp2;
                }
            }
        }
    }

    protected function getPathDistance(&$temp)
    {
        $current = 0;
        $distance = 0;
        foreach ($temp as $locationId) {
            $distance += $this->locations[$current]['dst'][$locationId];
            $current = $locationId;
        }

        $distance += $this->locations[$current]['dst'][$this->lcount - 1];
        return $distance;
    }
}