Longest path search algorithm

Published on Friday, April 6, 2012
PHP

The code tries to find a path that gives profit, for example. If we got a tree with three nodes that are all connected we want to find a path that leads to that we have to pay less each time we walk it.

$start = 1;
$end = array();
 
// Longest path algorithm
$array_vertices =
array(
array(1,7,3),
array(7,6,4),
array(6,1,1/5),
array(8,6,100),
array(7,5,5),
array(5,4,3),
array(4,2,1),
array(2,5,1/4),
array(2,1,1/7)
);
 
$start_connected = array();
foreach($array_vertices as $v)
{
   if($v[1] == $end[0] && $v[0] != $origin[0])
   {
      echo $v[0] . " ";
      $vinst *= (double)$v[2];
      $step[] = $v;
      if($v[0] == $start)
      {
         if($vinst > 1) {
            $ended = true;
            break;
         }
         else
         {
            $endedWithoutProfit = true;
            break;
         }
      }
      $end = $v;
   }
   unset($temp_connected[$v[0]][$v[1]]);
}
 
if(count($temp_connected) <= 0="" ||="" $endedwithoutprofit)="" {="" $ended="false;" $start_connected="array();" if(!$endedwithoutprofit)="" foreach($array_vertices="" as="" $v)="" if($v[1]="=" $start="" &&="" $v="" !="$end)" $start_connected[$v[0]][$v[1]]="true;" }="" $temp_connected="$start_connected;" if(count($start_connected)="=" if($endedwithoutprofit="" $vinst="" <="1)" findend(&$array_vertices,="" &$start,="" &$end,="" &$origin);="" if(count($end)="=" 0)="" if($vinst="" $error['noprofit']="Ended without profit" ;="" else="" $error['notfound']="Could not find a path" break;="" $error['noconn']="There is no path" $connected="array();" $end[0])="" $connected[$v[0]][$v[1]]="true;" if(count($connected)="=" $step="array();" $step[]="$end;" $endedwithoutprofit="false;" *="$end[2];" foreach($step="" $s)="" echo="" "from:="" $s[0]="" to="" $s[1],="" weight:="" $s[2]";="" "vinst:="" $vinst";="" if($error)="" foreach($error="" $e)="" "$e";="" function="" findend($array_vertices,="" *$array_nodes,*="" $start,="" $end,="" $prev)="" $max="NULL;" $i="0;" $unset="-1;" $end="null;" $prev="" ($max="=" null="" $v[2]=""> $max))
      {
         $end = $v;
         $max = $v[2];
      }
 
      if($prev == $v)
         $unset = $i;
      $i++;
   }
 
   if($unset > -1)
   {
      $prev = $end;
      unset($array_vertices[$unset]);
   }
}
comments powered by Disqus