PHP exercise cheapest flight

user_14299372 0
Viewed 201

So i want to find the cheapest flight with as many as stopover necessary in a PHP function.

$flights = [
["departure" => "BRI", "arrival" => "BDS", "price" => 20],
["departure" => "BRI", "arrival" => "ANC", "price" => 5],
["departure" => "ANC", "arrival" => "CRV", "price" => 3],
["departure" => "CRV", "arrival" => "BDS", "price" => 4],
["departure" => "CRV", "arrival" => "BRI", "price" => 2],
["departure" => "CRV", "arrival" => "XLR", "price" => 3],
["departure" => "SUF", "arrival" => "BDS", "price" => 5],
["departure" => "FLR", "arrival" => "NAP", "price" => 10],
["departure" => "FLR", "arrival" => "BDS", "price" => 1],
["departure" => "FLR", "arrival" => "FRA", "price" => 5],
["departure" => "NAP", "arrival" => "CRV", "price" => 12],
["departure" => "NAP", "arrival" => "BDS", "price" => 16],
["departure" => "NAP", "arrival" => "FLR", "price" => 1],
["departure" => "XLR", "arrival" => "BRI", "price" => 3],
["departure" => "BOL", "arrival" => "FRA", "price" => 3],
["departure" => "BOL", "arrival" => "FLR", "price" => 10],
["departure" => "FRA", "arrival" => "NAP", "price" => 3],

Assuming this table the function with "BRI" --> "BDS" should give me "12" (BRI->ANC, ANC->CRV CRV->BDS)

function giveMeLower($departure, $arrival) { global $flights; $price = 0;

foreach ($flights as $flight) {
    if (($flight["departure"] == $departure) and ($flight["arrival"] == $arrival)) {
        $price = $flight["price"];
    }
}

foreach ($flights as $volo) {
    if (($volo["departure"] == $departure)) {

        $tempPrice = $volo["price"];
        $scalo = $volo["arrival"];

        foreach ($flights as $volo_int) {
            if (($volo_int["departure"] == $scalo) and $volo_int["arrival"] == $arrival) {
                $tempPrice += $volo_int["price"];
                if ($tempPrice < $price || $price == 0) {
                    $price = $tempPrice;
                }
            }
        }
    }
}

return $price == 0 ? "No flight found" : $price;
}

This is what i tried, it works but only with one stopover.

Some suggestion to make it go as long as it can?

Thanks!

php
1 Answers

Yuya Aratani, did a great job on this I think. Adapt from Dijkstra's algorithm.

The "Graph" class is simple and efficient. And it does exactly the job you want!

require 'src/Graph.php';

$graph = Taniko\Dijkstra\Graph::create();

$graph
    ->add('BRI', 'BDS', 20)
    ->add('BRI', 'ANC', 5)
    ->add('ANC', 'CRV', 3)
    ->add('CRV', 'BDS', 4)
    ->add('CRV', 'BRI', 2, false)
    ->add('CRV', 'XLR', 3)
    ->add('SUF', 'BDS', 5)
    ->add('FLR', 'NAP', 10)
    ->add('FLR', 'BDS', 1)
    ->add('FLR', 'FRA', 5)
    ->add('NAP', 'CRV', 12)
    ->add('NAP', 'BDS', 16)
    ->add('NAP', 'FLR', 1)
    ->add('XLR', 'BRI', 3, false)
    ->add('BOL', 'FRA', 3)
    ->add('BOL', 'FLR', 10)
    ->add('FRA', 'NAP', 3);

$route = $graph->search('BRI', 'BDS');
$cost  = $graph->cost($route);

Returns

var_dump($route);//array(4) { [0]=> string(3) "BRI" [1]=> string(3) "ANC" [2]=> string(3) "CRV" [3]=> string(3) "BDS" }
echo $cost;//12
user_152530860
Related