ბელმან-ფორდის ალგორითმი

ბელმან-ფორდის ალგორითმი, ზოგჯერ მოხსენიებული როგორც ჭდის კორექციის ალგორითმი — ალგრითმი, რომელიც პოულობს უმოკლესს გზას გრაფში (გრაფის გვერდის შეფასება შეიძლება იყოს უარყოფითიც). დეიქსტრას ალგორითმიც იგივე პრობლემას ჭრის უფრო ნაკლებ დროში, მაგრამ მოითხოვს რომ გრაფის გვერდის შეფასება არ იყოს უარყოფითი. აქედან გამომდინარე ბელმან-ფორდის ალგორითმი გამოიყენება მაშინ, როდესაც გვერდის შეფასება არის უარყოფითი.

თუ გრაფი შეიცავს უარყოფითი შეფასებების ციკლს, ალგორითმს შეიძლია მხოლოდ ამოიცნოს ეს. ამ შემთხვევაში ალგორითმი ვერ პოულობს უმოკლეს გზას რომელშიც არ მეორდება არც ერთი წვერო.

ალგორითმი

ბელმან-ფორდის ალგორითმი ძალიან წააგავს დეიქსტრას ალგორითმს, მაგრამ იმის მაგივრად რომ მონიშნოს მინიმალურად შეფასებული წვერო რელაქსაციამდე, ის უბრალოდ აკეთებს ყველა გვერდის რელაქსაციას. აკეთებს ამას |V| − 1-ჯერ, სადაც |V| არის გრაფში წვეროების რაოდენობა. ალგორითმის ასიმპტოტიკური სირთულეა |O](|V|·|E|) სადაც |V| და |E| შესაბამისად არის წვეროების და გვერდების რაოდენობა გრაფში. ქვემოთ მოცემულია ბელმან-ფორდის ალგორითმი რეალიზებული ფსევდოკოდში:

procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: Initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null
   
   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:       
       for each edge uv in edges:
           u := uv.source
           v := uv.destination             // uv is the edge from u to v
           if v.distance > u.distance + uv.weight:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: check for negative-weight cycles
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if v.distance > u.distance + uv.weight:
           error "Graph contains a negative-weight cycle"

იმპლემენტაცია

იმპლემენტაცია 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;
}

იმპლემენტაცია 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);

რესურსები ინტერნეტში

• ინტერაქტიული ჯავა აპლეტი დაარქივებული 2007-10-14 საიტზე Wayback Machine.
• ალგორითმის რეალიზაციის მაგალითი