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);

