I've used the Graph module here, but there are probably others that could do the same thing.

use Graph;
use strict;
use warnings;

my $g = Graph->new;

$g->add_edges(
    [0,1],
    [0,1],
    [0,1],
    [1,344],
    [1,202],
    [1,300],
    [2,3],
    [3,4],
    [4,202],
    [4,345],
    [4,5],
    [4,6],
    [5,440],
    [5,500],
    [5,508],
    [5,6],
    [5,505],
    [6,7],
    [6,201],
    [6,507],
    [6,503],
    [7,503],
    [7,2],
    [7,507],
    [7,200],
    [200,202],
    [202,201],
    [202,2],
    [300,2],
    [300,344],
    [300,502],
    [300,506],
    [300,202],
    [344,300],
    [345,4],
    [440,5],
    [500,5],
    [502,300],
    [503,6],
    [503,7],
    [505,5],
    [506,300],
    [507,6],
    [507,7],
    [508,6],
);

my $apsp = $g->all_pairs_shortest_paths;

my @V = sort { $a <=> $b } $g->vertices;
my %V; @V{@V}=@V;

print <<EOF;
The graph has the following states:

@V

Valid state transitions are:

$g

EOF

while (1)
{
    print "Enter a sequence of states on a single line. (blank line to
+ exit)\n";
    local @ARGV;
    $_ = <>; chomp;
    my @P = split /\D+/;
    @P or last;
    grep { not exists $V{$_} } @P and warn("Sorry, at least one of tho
+se is not a valid state.\n"), next;

    for my $i ( 0 .. $#P-1 )
    {
        my @p2 = ( $P[$i], $P[$i+1] );
        my @PV = $apsp->path_vertices(@p2);
        @PV < 2 and print("The given state transition (@p2) is not val
+id in the given graph.\n"), next;
        $PV[0] eq $p2[0] && $PV[-1] eq $p2[-1] or warn("Bogus! (@p2) -
+> (@PV)!\n"), next;
        shift @PV; pop @PV;
        @PV and print "The given state transition (@p2) skips some sta
+tes: (@PV)\n";
    }
}
[download]

Update: Moved the $apsp assignment out of the loop.