Bellman-Fordův algoritmus

Z Wikipedie, otevřené encyklopedie

Tento algoritmus počítá nejkratší cestu v ohodnoceném grafu, kde mohou být některé hrany ohodnoceny záporně. Dijkstrův algoritmus tento problém řeší v kratším čase, ale vyžaduje nezáporné ohodnocení hran. Proto se Bellman-Fordův algoritmus používá i pro grafy se záporně ohodnocenými hranami.

Složitost algoritmu je O(V·E), kde V je počet vrcholů a E počet hran.

Algoritmus je používán ve směrovacím protokolu RIP.

[editovat] Implementace - Perl

#!/usr/bin/perl

use warnings;
use strict;

my $INFINITY = 10**24;

print „bellman-forduv algoritmus\n“;

my $graf = {
  pocatek => 'a', 
  hrany => [
        { from => 'a', to => 'b', capacity => 10 },
        { from => 'b', to => 'c', capacity => -20 },
        { from => 'c', to => 'd', capacity => 10 },
        { from => 'a', to => 'd', capacity => '10' },
        { from => 'd', to => 'e', capacity => -5 },
        { from => 'e', to => 'f', capacity => '10' },
        { from => 'f', to => 'g', capacity => -5 },
        { from => 'g', to => 'h', capacity => '10' },
        { from => 'h', to => 'i', capacity => '-30' },
        { from => 'i', to => 'j', capacity => '10' },
        { from => 'i', to => 'b', capacity => '-100' },
        { from => 'a', to => 'i', capacity => '10' },
  ], 
  vrcholy => [qw(a b c d e f g h i j)],
};


my %distance = ();
my %predek = ();

my ($vrchol, $hrana);

foreach $vrchol ( @{ $graf->{vrcholy} } )
{
        $distance{ $vrchol } = $INFINITY;
}
$distance{ $graf->{pocatek} } = 0;

foreach $vrchol ( @{ $graf->{vrcholy} } )
{
        foreach $hrana ( @{ $graf->{hrany} } )
        {
                if( $distance{ $hrana->{from} } != $INFINITY ) {
                        my $new_distance = $distance{ $hrana->{from} } + $hrana->{capacity}; 
                        if( $new_distance < $distance{ $hrana->{to} } ) 
                        {
                                $distance{ $hrana->{to} } = $new_distance;
                                $predek{ $hrana->{to} } = $hrana->{from};
                        }
                }
        }
}

foreach $hrana ( @{ $graf->{hrany} } )
{
        if ( $distance{ $hrana->{to} } > $distance{ $hrana->{from} } + $hrana->{capacity} )
        {
                print „Negative edge weight cycles detected!\n“;
                exit(1);
        }
}

foreach $vrchol ( @{ $graf->{vrcholy} } )
{
        print „The shortest distance between nodes “ 
                . $graf->{pocatek} . " and $vrchol is " . $distance{$vrchol}
                . „\n“;
        # vypis cestu 
        my $cesta = "";
        my $p = $vrchol;
        while( $p ) {
                $cesta .= "$p >- ";
                $p = $predek{$p};
        }
        print reverse( $cesta ) . "\n";
}

exit(0);