Combinations in multidimensional array keeping the keys PHP

I have a problem with site transport. I have to combine all arrays preserving the keys and extrapolate all the combinations.
The internal values must not repeat and must combine in order.

The internal values are the bus stops and they are adjacent. example Location 58 to location 61, location 61 to location 140 and so on. this is how metro stops work.

I get on the bus at the stop id_sott=58 and I have to go to the stop id_sott=65.

id_sott 58 to id_sott=65.

the foreign keys (in this case 1, 66, 68) are very important because they are groups of hours that the bus or metro passes.

What routes are available?

I need a route with times

This is my array

$arrayxcorse=array ( 
'1' => array (  '58', '61',  '140',  '142', '91',  '118',  '65' ),
'66' => array (  '140', '62', '91', '65' ),
'68' => array (  '65' ,'140',  '58',  '142' )
);

From start and end, I want these combinations:

$start=58;
$end=65;


combination1= array( '58', '61',  '140',  '142', '91',  '118',  '65' );

combination2= array('1' => array ( '58', '61',  '140'), '66' => array ( '140', '62', '91','65'));

combination3= array('68' => array ( '58','142'), '1' => array ('142', '91', '118','65' ) );

I thought about creating a recursive and merge function but it’s wrong. with this function and with a flat array I don’t have the key

$arrayxcorse=['58-61','61-140','140-142','142-91','91-118','118-65','140-62','62-91 ','91-65','65-140','140-58','58-142'];



$start=$_GET['par'];
$end=$_GET['arr'];

function ctr_doppioni($path,$ultimo){

 $tuttiiprimi=[];
 $tuttisecondi=[];
 $flag=1;
   for($u=0;$u<count($path);$u++){
     $thsval=explode("-",$path[$u]);
     $tuttiiprimi[$thsval[0]][]=$thsval[0];
     $tuttisecondi[$thsval[1]][]=$thsval[1];


     if(count($tuttiiprimi[$thsval[0]])>1 || count($tuttisecondi[$thsval[1]])>1 || ($u<count($path)-1 && ($thsval[0]==$ultimo || $thsval[1] ==$ultimo) )  ){
       $flag=0;
       $u=count($path)-1;//esco
     }
   }
   return $flag;
 }

function getPathTo2(array $array, string $pathEndsWith, string $linkOn = '', $path = [], &$result = []) {


        foreach ($array as $hyphenated) {
            sscanf($hyphenated, '%[^-]-%s', $first, $second);


            if ($first === $linkOn) {

                  if ($pathEndsWith === $second) {
                     $flag=ctr_doppioni($path,$pathEndsWith);
                     if($flag==1){ $result[] = array_merge($path, [$hyphenated]); }
                  }


                    getPathTo2(array_diff($array, [$hyphenated]), $pathEndsWith, $second, array_merge($path, [$hyphenated]), $result);

              }


            }

        return $result;
    }


    $percorsi[]=getPathTo2($arrayxcorse,$end,$start);
    print_r($percorsi);

i saw something similar here but couldn’t adapt
Array permutations in multidimensional array keeping the keys PHP

Thanks for your help