Code golf anyone?
#!/usr/bin/perl
use File::Spec;
my $g;
my $f = shift;
while (1) {
    print $f;
    $g = readlink($f);
    last unless defined $g;
    printf " -> %s\n", $g;
    $f =~ s,/[^/]*$,,;
    $f = File::Spec->rel2abs($g, $f);
}
print "\n";
Ok, how about this:
#!/usr/bin/perl
use File::Spec;
sub r {
    my ($p, $s) = @_;
    my $l = readlink $p;
    if ($l) {
        printf "%s -> %s\n", $p, $l;
        $p =~ s,/[^/]*$,,;
        r("",File::Spec->rel2abs($l,$p) . $s)
    } else {
        $s =~ s!^(/?[^/]+)(.*)! r($p.$1, $2) !e;
    }
}
r("",shift);
The output is not quite as described but it's understandable.  And dig that craaazy recursive executable regexp substitution!