#!/usr/bin/perl

use 5.040;

my $N = 40;   # número de puntos
say "$N puntos";

# coordenadas

my (@x, @y);
for my $i (1..$N){
    $x[$i] = 100*rand();
    $y[$i] = 100*rand();
}

# distancias

my @d;
for my $i (1..$N){
    for my $j (1..$N){
	$d[$i][$j] = sqrt( ($x[$i]-$x[$j])**2 + ($y[$i]-$y[$j])**2 );
    }
}

# distancias no factibles 

my $M = 600;
say "De ", $N*($N-1), " distancias, se toman ",$M*2, " como rutas imposibles"; 

for my $k (1..$M){
repeat:    
    my $i = int( rand()*100 );
    my $j = int( rand()*100 );
    if ($i != $j){
	$d[$i][$j] = -1;
	$d[$j][$i] = -1;   # hay que meterle mucha caña para que derive en transbordos
    }else{
	goto repeat if ($k <= $M);
    }
}

# main rutas 

my @rutas;
my $dist = 0;
for my $i (1..$N){
    say "";
    for my $j (1..$N){
	next if ($i == $j);
	say "Rutas de $i a $j:";
	$rutas[$i][$j] = nodijkstra( $i, $j );
	say $rutas[$i][$j];
    }
}

exit 2;


sub nodijkstra {
    my ($x, $y) = @_;
    my $count = 0;
   
again:                                    
    my $solant;
    my $sol = 0;                      # recursivo pero a mano
    my $min = 9e10;
    $dist = 0;
    my $i = $x;
    for my $j (1.. $N){
	next if $i == $j;
	next if $d[$i][$j] == -1;
	if ($d[$i][$j] > 0){
	    if ($j == $y){
		$sol = "OK";
		$dist += $d[$i][$j];
		say "De $i a $j conseguido con distancia $dist"; 
		return $sol;
	    }else{
		if ($d[$i][$j] < $min){		    
		    $solant = $sol if $sol;            # para version 2
		    $sol = $j;
		    $min = $d[$i][$j];
		}
	    }
	}
    }
    if (++$count >= $N){                   # bucle infinito
	$sol = "NO ENCUENTRO SOLUCIÓN";
	return $sol;
    }
    if ($sol > 0){
	say "$x a $y se cambia por $x a $sol y se busca $sol a $y";
	$dist += $d[$x][$sol];
	$x = $sol;                      # puede no ser el mejor, es el más próximo a $i
	goto again;
    }
    die "ERROR en algoritmo";
}
	    
    
__END__    

#	}elsif ($d[$i][$j] == -1){
#	    next;
#	}elsif ($d[$i][$j] == 0){
#	    next; No puede pasar
#	}else{
#	    die "Error de algoritmo";  La matriz de distancias no se vuelve a escribir, es segura

Bueno, esto es una prueba de concepto de que es posible construir 
  un algoritmo (rápido) de búsqueda de rutas con o sin transbordos
  ante una matriz de distancias dañada en la que no todas las 
  rutas sean posibles.