Zobrazení zdroje stránky Bellmanův–Fordův algoritmus

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

Algoritmus je používán například ve směrovacím protokolu [[Routing Information Protocol|RIP]].

== Popis algoritmu ==
V&nbsp;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 <math>S</math>. Jestliže je zjištěno, že hodnota v&nbsp;uzlu je vyšší než hodnota z&nbsp;nynějšího uzlu plus ohodnocení hrany z&nbsp;nynějšího uzlu do&nbsp;uzlu, v&nbsp;kterém bychom chtěli změnit jeho hodnotu, pak tuto hodnotu změníme (snížíme). Hlavní rozdíl oproti [[Dijkstrův algoritmus|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&nbsp;poté ho už neupravuje. Toto se v&nbsp;Bellmanově–Fordově algoritmu neděje, jelikož tyto uzly neuzavírá takto ihned, ale prochází několikrát všechny uzly a&nbsp;upravuje postupně hodnoty vzdáleností nejkratších cest.

== Časová složitost ==
[[Asymptotická složitost|Časová složitost algoritmu]] je <math>O(V \cdot E)</math>, kde <math>V</math> je počet vrcholů a&nbsp;<math>E</math> počet hran.

== Implementace ==

=== Obecná implementace v pseudokódu ===
<pre>
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 < v.vzdálenost
      v.vzdálenost := u.vzdálenost + h.délka
      v.předchůdce := u

// krok 3: kontrola záporných cyklů
for each h in hrany
  u := h.počátek
  v := h.konec
  if u.vzdálenost + h.délka < v.vzdálenost
    error "Graf obsahuje záporný cyklus."
</pre>

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&nbsp;ostatními uzly. 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&nbsp;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&nbsp;hodnoty vykonstruované algoritmem nemůžeme brát za správné.

=== Implementace – Perl ===
<syntaxhighlight lang="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 < $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 ) {
		push @cesta, $p;
		$p = $predek{$p};
	}
	print " " . join(" -> ", reverse( @cesta )) . "\n";
}

exit(0);
</syntaxhighlight>

=== Implementace – C ===
<syntaxhighlight lang="c">
# include <limits.h>
# include <stdio.h>
# include <stdlib.h>

/* Let INFINITY be an integer value not likely to be
   confused with a real weight, even a negative one. */
# define INFINITY ((1 << 14)-1)

typedef struct {
    int source;
    int dest;
    int weight;
} Edge;

void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
{
    int *distance = malloc(nodecount * sizeof *distance);
    int i, j;
    for (i=0; i < nodecount; ++i)
      distance[i] = INFINITY;
    distance[source] = 0;

    for (i=0; i < nodecount; ++i) {
        for (j=0; j < edgecount; ++j) {
            if (distance[edges[j].source] != INFINITY) {
                int new_distance = distance[edges[j].source] + edges[j].weight;
                if (new_distance < distance[edges[j].dest])
                  distance[edges[j].dest] = new_distance;
            }
        }
    }

    for (i=0; i < edgecount; ++i) {
        if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
            puts("Negative edge weight cycles detected!");
            free(distance);
            return;
        }
    }

    for (i=0; i < nodecount; ++i) {
        printf("The shortest distance between nodes %d and %d is %d\n",
            source, i, distance[i]);
    }
    free(distance);
    return;
}

int main(void)
{
    /* This test case should produce the distances 2, 4, 7, -2, and 0. */
    Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},
                      {2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},
                      {4,0, 6}, {4,2, 7}};
    BellmanFord(edges, 10, 5, 4);
    return 0;
}
</syntaxhighlight>

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

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