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$. 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 < 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."

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

Implementace – 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;
}

Externí odkazy

• Obrázky, zvuky či videa k tématu Bellmanův-Fordův algoritmus na Wikimedia Commons
• Interaktivní demonstrace
• Jakub Černý: Základní grafové algoritmy (texty v pdf)