Implementation de Dijkstra en PERL

Pour les besoin du concours de CodinGame, la Tron Battle j’ai implémenté l’algorithme de Dijkstra en PERL.

Pourquoi c’est algorithme ? Celui-ci permet de calculé le plus court chemin entre deux noeud. Mon but étant de me rapprocher le plus rapidement de mon adversaire pour le limiter dans ses mouvement. Comme on le dit souvent, la meilleurs défense c’est l’attaque !

#!/usr/bin/perl

sub array_diff(\@\@) {
    my %e = map { $_ => undef } @{$_[1]};
    return @{[ ( grep { (exists $e{$_}) ? ( delete $e{$_} ) : ( 1 ) } @{ $_[0] } ), keys %e ] };
}

sub in_array
{
     my ($arr,$search_for) = @_;
     my %items = map {$_ => 1} @$arr; 
     return (exists($items{$search_for}))?1:0;
}

sub array_unique
{
    my %seen = ();
    @_ = grep { ! $seen{ $_ }++ } @_;
}

sub dijkstra {
    my ($graph_arrayHash, $source, $target) = @_;
    my @graph_array = @$graph_arrayHash;
    my @vertices;
    my %neighbours;
    my %previous;

    foreach  $edge (@graph_array) {
        push(@vertices, @$edge[0]);
        push(@vertices, @$edge[1]);
        $neighbours{@$edge[0]}->{@$edge[1]} = @$edge[2];
    }

    @vertices = array_unique(@vertices);

    foreach $vertex (@vertices) {
        $dist{$vertex} = inf;
        $previous{$vertex} = undef;
    }

    $dist{$source} = 0;

    while (@vertices > 0) 
    {
        $min = inf;
        foreach $vertex (@vertices){
            if ($dist{$vertex} < $min) {
                $min = $dist{$vertex};
                $u = $vertex;
            }
        }

        $diff = [ $u ];
        if (in_array(\@vertices, $u))
        {
            @vertices = array_diff(@vertices, @$diff);    
        }

        if ($dist{$u} == inf or $u == $target) {
            last;
        }

        if (defined($neighbours{$u})) {
            foreach $next (keys %{$neighbours{$u}}) {
                $alt = $dist{$u} + $neighbours{$u}->{$next};
                if ($alt < $dist{$next}) {
                    $dist{$next} = $alt;
                    $previous{$next} = $u;
                }
                delete $neighbours{$next}->{$u};
            }
        }
    }

    @path;
    $u = $target;

    while (defined($previous{$u})) {
        unshift(@path, $u);
        $u = $previous{$u};
    }
    unshift(@path, $u);
    return \@path;
}

Voici un exemple d’utilisation :

$nodeList = [
    ["node_1", "node_2", 7],
    ["node_1", "node_3", 9],
    ["node_2", "node_4", 10],
    ["node_2", "node_1", 15],
    ["node_3", "node_1", 14],
    ["node_3", "node_5", 13],
    ["node_4", "node_2", 9],
    ["node_5", "node_6", 2]

];

$path = dijkstra($nodeList, "node_1", "node_6");

print Dumper($path);

Voici le résultat fournis :

$ perl dijkstra.pl
$VAR1 = [
          'node_1',
          'node_3',
          'node_5',
          'node_6'
        ];

Malheureusement pour moi ce script ne répond pas dans les délais impartie ^^ J’ai plus qu’à passer sur un autre algo tel que A*

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *