my @list; # Komibantionen ['start','ziel']
foreach my $start (keys %entfernung) {
   foreach my $ziel (keys %{$entfernung{$start}}) {
     push @list, [$start,$ziel];
   }
}

my @sorted_list = sort {$entfernung{$a->[0]}{$a->[1]} <=> $entfernung{$b->[0]}{$b->[1]}} @list;
printf "Von %s nach %s: %d\n", @$_, $entfernung{$_->[0]}{$_->[1]} foreach @sorted_list;