Bellmanův–Fordův algoritmus

Bellmanův-Fordův algoritmus počítá nejkratší cestu v ohodnoceném grafu z jednoho uzlu do uzlu dalšího (do ostatních uzlů), kde mohou být některé hrany ohodnoceny i záporně. Dijkstrův algoritmus tento problém řeší sice v kratším čase, ale vyžaduje nezáporné ohodnocené hrany. Proto se Bellmanův-Fordův algoritmus používá i pro grafy se záporně ohodnocenými hranami.

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

Popis algoritmu

V případě grafů se záporně ohodnocenými hranami není Dijkstrův algoritmus obecně vždy použitelný. Proto nasazujeme Bellmanův-Fordův algoritmus, který stejně jako Dijkstrův algoritmus využívá metodu relaxace hran, jež zjišťuje aktuálně nastavenou hodnotu nejkratší vzdálenosti od uzlu S. +more Jestliže je zjištěno, že hodnota v uzlu je vyšší než hodnota z nynějšího uzlu plus ohodnocení hrany z nynějšího uzlu do uzlu, v kterém bychom chtěli změnit jeho hodnotu, pak tuto hodnotu změníme (snížíme). Hlavní rozdíl oproti Dijkstrovu algoritmu spočívá ve způsobu průchodu grafu. Jelikož Dijkstrův algoritmus, jestliže projdeme všechny následníky jednoho uzlu, tak tento uzel „uzavře“ a poté ho už neupravuje. Toto se v Bellmanově-Fordově algoritmu neděje, jelikož tyto uzly neuzavírá takto ihned, ale prochází několikrát všechny uzly a upravuje postupně hodnoty vzdáleností nejkratších cest.

Časová složitost

Časová složitost algoritmu je O(V \cdot E), kde V je počet vrcholů a E počet hran.

Implementace

Obecná implementace v pseudokódu

bellman-ford(vrcholy, hrany, zdroj)

// krok 1: inicializace grafu for each v in vrcholy if v=zdroj then v.vzdálenost := 0 else v.vzdálenost := nekonečno v.předchůdce := null

// krok 2: opakovaně relaxovat hrany for i from 1 to size(vrcholy)-1 for each h in hrany // h je hrana z u do v u := h.počátek v := h.konec if u.vzdálenost + h.délka

První cyklus inicializuje graf - nastaví všem vrcholům kromě zdroje nekonečné vzdálenosti, zdroji nulovou. Druhý cyklus upravuje relaxací hodnoty vzdáleností nejkratších cest mezi zdrojem a ostatními uzly. +more Pokud třetí cyklus zjistí, že některá už určená hodnota nejkratší cesty mezi uzly by mohla být ještě zkrácena (snížena hodnota vzdálenosti nejkratší cesty), graf obsahuje záporně ohodnocený cyklus. V takovém případě postrádá úkol nalezení minimální cesty smysl (opakovaným průchodem cyklem získáme neomezeně krátkou cestu) a hodnoty vykonstruované algoritmem nemůžeme brát za správné.

Implementace - Perl

# !/usr/bin/perl

use warnings; use strict;

my $INFINITY = 10**24;

print "bellmanuv-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 {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} . +more " and $vrchol is " . $distance{$vrchol} . "\n"; # vypis cestu my @cesta = ; my $p = $vrchol; while( $p ) { push @cesta, $p; $p = $predek{$p}; } print " " . join(" -> ", reverse( @cesta )) . "\n"; }.

exit(0);

Implementace - C

# include # include # include

/* Let INFINITY be an integer value not likely to be confused with a real weight, even a negative one. */ # define INFINITY ((1 distance[edges[i]. +moresource] + edges[i]. weight) { puts("Negative edge weight cycles detected. "); free(distance); return; } }.

for (i=0; i

Externí odkazy

[url=https://web. archive. +moreorg/web/20071014012236/http://links. math. rpi. edu/applets/appindex/graphtheory. html]Interaktivní demonstrace[/url] * Jakub Černý: [url=https://web. archive. org/web/20071018060717/http://kam. mff. cuni. cz/~kuba/ka/]Základní grafové algoritmy[/url] (texty v pdf).

Kategorie:Grafové algoritmy Kategorie:Vzdálenosti v grafu