How to determine a long air route?

Question

Algorithms

Let's say there is a goal to fly an airplane and spend the most amount of time. And for greater simplicity of the picture, let's forget about the time, we only have dates and assume that each plane flies 1 day.
For example, we have information that there are the following airports:

• SVO
  
• M.A.D.
  
• DME
  
• BAR
  
• lon
  

And the following flights:

• SVO -> MAD 2018-06-10
  
• SVO -> BAR 2018-06-12
  
• MAD-> DME 2018-06-16
  
• MAD-> BAR 2018-06-17
  
• BAR -> LON 2018-06-18
  
• DME -> LON 2018-06-19
  

Answer 1

Someday it will come in handy for someone. As a result, I did not find a beautiful solution, it seems that it does not exist. Did it like this:

$Longest_Path = new CLongestPathBuilder($routes); // создаем экземпляр класса
$Longest_Path -> printLongestPath(); // выводим информацию о самом долгом маршруте



Class CLongestPathBuilder
{
  protected $arResult = [];
  protected $iterator = 0;

  function __construct($routes)
  {
    // Sorting routes array by date (dt_start field)
    try
    {
      $this->arResult['routes'] = CExtraTools::sortArrayByDate($routes);
    }
    catch(Exception $e)
    {
      echo $e->GetMessage();
      exit(1);
    }

    foreach($this->arResult['routes'] as $route)
    {
      $this->arResult['path'][$this->iterator]['full_path'] .= $route['start'].' -> '.$route['finish'];
      $this->arResult['path'][$this->iterator]['routes_count'] = 1; 
      // Trying to find all available routes from last destination ($route['finish'])
      $this->getRoutes($route);
      $this->iterator++;
    }
  }

  protected function getRoutes($route1)
  {
    // Get available routes from last destination
    if(!$this->arResult['path'][$this->iterator]['prev_date'])
    {
      $this->arResult['path'][$this->iterator]['prev_date'] = $route1['dt_start'];
    }
    foreach($this->arResult['routes'] as $route2) 
    {
      if( ($route1['start'] != $route2['start']) && ($route1['finish'] == $route2['start']) && ($this->arResult['path'][$this->iterator]['prev_date'] < $route2['dt_start']) )
      {
        $this->arResult['path'][$this->iterator]['full_path'] .= ' -> '.$route2['finish'];
        $this->arResult['path'][$this->iterator]['days'] += CExtraTools::diffDates($route1['dt_start'], $route2['dt_start']);
        $this->arResult['path'][$this->iterator]['dates'][] = $route1['dt_start'].' - '.$route2['dt_start'];
        $this->arResult['path'][$this->iterator]['prev_date'] = $route2['dt_start'];
        $this->arResult['path'][$this->iterator]['routes_count']++; // Number of routes in the path
        $this->setLongest($this->arResult['path'][$this->iterator]['days']); // Setting current path as the longest one
        $this->getRoutes($route2);
      }
    }
  }

  protected function setLongest($duration)
  {
    // a function used to set longest path
    if($duration > $this->arResult['longest_path']['days'])
    {
      $this->arResult['longest_path'] = $this->arResult['path'][$this->iterator];
    }
  }

  public function getLongest()
  {
    // a function used to get longest path
    return $this->arResult['longest_path'];
  }

  public function getPaths()
  {
    // a function used to get longest path
    return $this->arResult['path'];
  }

  public function printAllPaths()
  {
    CExtraTools::pre($this->arResult['path']);
  }

  public function printLongestPath()
  {
    CExtraTools::pre($this->arResult['longest_path']);
  }
}



Class CExtraTools
{
  public static function diffDates($date1, $date2)
  {
    // The function to count the difference between two dates
    try
    {
      $datetime1 = new DateTime($date1);
      $datetime2 = new DateTime($date2);
    }
    catch (Exception $e) {
      echo $e->getMessage();
      exit(1);
    }
    $interval = $datetime1->diff($datetime2);
    return $interval->invert ? $interval->days*(-1) : $interval->days;
  }

  public static function pre($var)
  {
    // modification of print_r method
    echo '<pre>';
    print_r($var);
    echo '</pre>';
  }

  protected static function cmp($a, $b)
  {
    // only to sort array in sortArrayByDate() function
    if ($a['dt_start'] == $b['dt_start']) {
      return 0;
    }
    return ($a['dt_start'] < $b['dt_start']) ? -1 : 1;
  }

  public static function sortArrayByDate($array)
  {
    // Sort array by date (dt_start field)
    if(!is_array($array))
    {
      throw new Exception('Должен быть передан массив');
    }
    usort($array, "self::cmp");
    return $array;
  }
}

Answer 2

https://en.wikipedia.org/wiki/Problem_about_the_longest...

Answer 3

I would venture to guess, I see it like this:
0. We take the data into an array, sort the array by date.
1. We take the smallest date - the airport of departure (SVO), store it in a variable
2. We take the largest date - the airport of flight. (DME), store in variable
3. Further (we understand that both airports are in Moscow, and we are homeless for 9 days.) - i.e. break; (if we take "long" - time, not "flight time") If not, then:
4. The first element of the array = the first flight in any case, we take the airport of arrival.
5. Iterate through the array in order from the second element (key = 1, not 0), check all elements for the condition "if the airport of departure = the last airport of arrival", if there are several of them, then the recursion of the same function (we build several routes in this case ) and so on until all recursions are completed.
6. after We take all the collected routes, look, if the last airport does not match the data from point 2 (arrival airport - DME), then delete these routes.
7. From the rest, we look at which of the routes has more flights and / or whose date of the last flight is longer (depending on what we take under "long" - flight time or number of flights)
I do not pretend to be the most optimal solution, probably, if you include some kind of math, then perhaps you can make the analysis faster\better\beautiful.