2022-06-10 / Bartłomiej Kurek
Algorytm Bellmana-Forda: najkrótsze ścieżki w grafie

W tym artykule zajmiemy się implementacją algorytmu Bellmana-Forda, którego zadaniem jest wyznaczenie najkrótszych ścieżek w skierowanym grafie ważonym. Ścieżki wyznaczane są z wierzchołka źródlowego do wszystkich pozostałych wierzchołków.

Omawiany kod znajdziemy w repozytorium git.

Wikipedia: Bellman–Ford algorithm.
Dobrym artykułem z przykładową implementacją w Python jest post na Favtutor.

Python

Omówienie algorytmu zaczniemy od prostej implementacji w Python.

Inicjalizacja dystansów i poprzedników

Inicjalizacja dystansów d na maksymalną wartość math.inf oraz ustawienie poprzednika (predecessor) P na None. Dystans do startowego wierzchołka s ustawiamy na 0.

import math

def initialize(G, s):
    d = {}
    P = {}
    for v in G.vertices:
        d[v] = math.inf
        P[v] = None
    d[s] = 0
    return d, P

Relaksacja

Algorytm wykorzystuje relaksację, której istotą jest zastępowanie dystansów coraz to lepszymi wartościami.
Najprostsza implementacja funkcji relaksacji wygląda następująco:

def relax(u, v, c, d, P):
    if d[v] > d[u] + c:
        d[v] = d[u] + c
        P[v] = u

Jeśli obecnie wyznaczony dystans d[v] jest większy niż dystans d[u] + koszt, to aktualizujemy wartość na tę sumę, a poprzednika ustawiamy na wierzchołek u.

Algorytm

Kiedy mamy przygotowane funkcje inicjalizacji i relaksacji, cały algorytm możemy sprowadzić do kodu zaprezentowanego w poniższym krótkim listingu:

def bellman_ford(G, s):
    assert s in G.vertices, "No such vertex: %s" % s
    d, P = initialize(G, s)

    for _ in range(G.size - 1):
        for u, v, c in G.edges:
            relax(u, v, c, d, P)

    # Check cycles
    for u, v, c in G.edges:
        if d[v] > d[u] + c:
            return

    return d, P

Funkcja przyjmuje graf G oraz początkowy wierzchołek s. Następnie inicjalizujemy wartości dystansów i poprzedników.
W kolejnym kroku dla każdego wierzchołka wykonujemy funkcję relaksacji. Relaksacji dokonujemy do wyczerpania wierzchołków (stąd pętla w pętli).

Jeśli w grafie znajdzie się cykl, algorytm nie zwróci żadnego wyniku.

Sam graf G możemy zaimplementować jako trywialną klasę:

    class G:
        vertices = [0, 1, 2, 3, 4]
        size = len([0, 1, 2, 3, 4])
        edges = [
            (0, 1, 2),
            (0, 2, 4),
            (1, 3, 2),
            (2, 3, 4),
            (2, 4, 3),
            (4, 3, -5),
        ]

Sprawdzamy wykonanie implementacji Python:

if __name__ == "__main__":
    """
    D                   P
----------------------------
    0                   0
    1                   2
    2                   4
    3                   2
    4                   7
    """

    """
         1 -- (2) -- 3 ---
        /           /      \
      (2)         (4)      (-5)
      /           /          |
     0 -- (4) -- 2 -- (3) -- 4
    """

    s = 0
    d, P = bellman_ford(G, s)
    for v in G.vertices:
        print((s, v), " -> ", ("!" if P[v] is None else P[v]), "Distance:", d[v])

Po uruchomieniu otrzymujemy wynik:

(0, 0)  ->  ! Dist: 0
(0, 1)  ->  0 Dist: 2
(0, 2)  ->  0 Dist: 4
(0, 3)  ->  4 Dist: 2
(0, 4)  ->  2 Dist: 7

Graf z artykułu na Wikipedii

Sprawdźmy również wykonanie algorytmu w Python dla grafu prezentowanego w artykule na Wikipedii.




(Image: CC BY-SA 4.0, Michel Bakni - (2013,) Graph Theory for Operations Research and Management: Applications in Industrial Engineering, p. 161 DOI: 10.4018/978-1-4666-2661-4. ISBN: 1466626615)


Graf zapisany jako trywialna klasa w Python:

    class G:
        vertices = [0, 1, 2, 3, 4]
        size = len([0, 1, 2, 3, 4])
        edges = [
            (0, 1, 9),
            (0, 2, 3),

            (1, 2, 6),
            (1, 4, 2),

            (2, 1, 2),
            (2, 3, 1),

            (3, 2, 2),
            (3, 4, 2),
        ]

Po uruchomieniu z wierzchołkiem źródłowym 0 otrzymujemy wynik:

(0, 0)  ->  ! Dist: 0
(0, 1)  ->  2 Dist: 5
(0, 2)  ->  0 Dist: 3
(0, 3)  ->  2 Dist: 4
(0, 4)  ->  3 Dist: 6

Postgres

Schemat

Tabela reprezentująca krawędzie grafu oraz ich wagi:

CREATE TABLE graph (
       edge_id SERIAL PRIMARY KEY,
       src INTEGER NOT NULL,
       dst INTEGER NOT NULL,
       weight NUMERIC(12,3) NOT NULL
);

Tabela, w której przechowywane będą dystanse:

CREATE TABLE _bf_distances (
       v INTEGER,
       distance NUMERIC NOT NULL
);

Tabela poprzedników:

CREATE TABLE _bf_predecessors (
       v INTEGER,
       prev NUMERIC
);

Implementacja algorytmu

Algorytm zaimplementujemy jako funkcję plpgsql, która zwracać będzie zestaw rekordów pomocniczego typu bf_result_t.

Typ:

CREATE TYPE bf_result_t AS (
       v INTEGER,
       distance NUMERIC
);

Funkcja PLPGSQL:

CREATE OR REPLACE FUNCTION bellman_ford(src_ INTEGER)
RETURNS SETOF bf_result_t
AS $$
DECLARE
    tmp_ INTEGER;  -- used only for iterating vertices
    u_ INTEGER;    -- src node during iteration
    v_ INTEGER;    -- dst node during iteration
    w_ NUMERIC;    -- weight/cost of a given node

    dv_ NUMERIC;   -- distance stored for v
    du_ NUMERIC;   -- distance stored for u
BEGIN

    -- Initialization:
    --   select all vertices (array of arrays[src, node]),
    --   create a single column and select distinct elements
    FOR tmp_ IN SELECT DISTINCT(UNNEST(array_agg(ARRAY[src, dst]))) FROM graph
    LOOP
       INSERT INTO _bf_distances VALUES(tmp_, 2147483647);       -- set max int
       INSERT INTO _bf_predecessors VALUES(tmp_, NULL);          -- set NULL for current vertex
    END LOOP;

    UPDATE _bf_distances SET distance = 0 WHERE v = src_;     -- start distance


    -- ALGORITHM:
    -- for all vertices
    FOR tmp_ IN SELECT DISTINCT(UNNEST(array_agg(ARRAY[src, dst])))
           FROM graph
    LOOP
        -- for all edges
        FOR u_, v_, w_ IN SELECT src, dst, weight  FROM graph
        LOOP
                -- RELAXATION
                SELECT distance FROM _bf_distances WHERE v = v_ INTO dv_;
                SELECT distance FROM _bf_distances WHERE v = u_ INTO du_;
                IF dv_ > du_ + w_ THEN
                   -- update distance for current v
                   UPDATE _bf_distances SET distance = du_ + w_ WHERE v = v_;
                   -- set predecessor of v to u
                   UPDATE _bf_predecessors SET prev = u_ WHERE v = v_;
                END IF;
        END LOOP;
    END LOOP;


    -- Check cycles
    FOR u_, v_, w_ IN SELECT src, dst, weight  FROM graph
    LOOP
        SELECT distance FROM _bf_distances WHERE v = v_ INTO dv_;
        SELECT distance FROM _bf_distances WHERE v = u_ INTO du_;
        IF dv_ > du_ + w_ THEN
           RETURN;  -- if cycle was found, don't return any result
        END IF;
    END LOOP;

    RETURN QUERY SELECT * FROM _bf_distances ORDER BY v;
END
$$
LANGUAGE plpgsql;

Omówienie implementacji

Inicjalizacja

W celu inicjalizacji dystansów wybieramy z grafu wszystkie unikalne wierzchołki (zarówno źródłowe jak i docelowe /src, dst/). Do realizacji tego możemy użyć funkcji UNNEST(). Możemy to prześledzić krok po kroku:

  • Uzyskanie tablicy tablic (array_agg(ARRAY[...])):
bftest=> SELECT array_agg(ARRAY[src, dst]) FROM graph;
                     array_agg                     
---------------------------------------------------
 {{0,1},{0,2},{1,2},{1,4},{2,1},{2,3},{3,2},{3,4}}
(1 row)
  • Rozwinięcie wszystkich wierzchołków do poszczególnych rekordów (UNNEST()):
bftest=> SELECT UNNEST(array_agg(ARRAY[src, dst])) FROM graph;
 unnest 
--------
      0
      1
      0
      2
      1
      2
      1
      4
      2
      1
      2
      3
      3
      2
      3
      4
(16 rows)
  • Wyłuskanie unikalnych wierzchołków (DISTINCT):
bftest=> SELECT DISTINCT(UNNEST(array_agg(ARRAY[src, dst]))) FROM graph;
 unnest 
--------
      0
      1
      2
      3
      4
(5 rows)

Dla wszystkich unikalnych wierzchołków ustawiamy dystans na maksymalną wartość typu INT, a poprzedników ustawiamy na NULL.

Relaksacja

W dalszej części algorytmu przetwarzamy wszystkie unikalne wierzchołki i dla każdej krawędzi wykonujemy relaksację.
W tym celu do zmiennych dv_ oraz du_ przypisujemy ich aktualne dystanse, a następnie sprawdzamy czy znaleźliśmy ścieżkę o niższym koszcie. Jeśli tak, to aktualizujemy dystans oraz ustawiamy poprzednika.

Sprawdzenie cykli

Sprawdzenie cykli nie różni się w żaden sposób od wcześniej przedstawionej implementacji w języku Python. Dla wszystkich wierzchołków sprawdzamy czy relaksacja byłaby możliwa. W takim przypadku wychodzimy z funkcji bez zwracania jakichkolwiek rekordów.

Zwracanie wyników

Funkcja zwraca zbiór rekordów (SETOF) typu bf_result_t, zatem możemy po prostu wykorzystać tutaj "RETURN QUERY".

Uruchomienie

Analogicznie jak w przypadku Python, wykorzystamy te same przykładowe grafy.

Przykład 1

Ładujemy dane grafu:

INSERT INTO graph(src, dst, weight) VALUES
       (0, 1, 2.0),
       (0, 2, 4.0),
       (1, 3, 2.0),
       (2, 4, 3.0),
       (2, 3, 4.0),
       (4, 3, -5.0);

Wykonujemy algorytm:

$ dropdb --if-exists bftest;
$ createdb bftest;
$ psql -1q bftest < schema.sql
$ psql -1q bftest < graph-simple.sql
$ psql -1q bftest < bellman-ford.sql 
$ psql bftest -c "SELECT * FROM bellman_ford(0)"
 v | distance 
---+----------
 0 |        0
 1 |    2.000
 2 |    4.000
 3 |    2.000
 4 |    7.000
(5 rows)

Przykład 2: graf z Wikipedii

Dane:

INSERT INTO graph(src, dst, weight) VALUES
       (0, 1, 9),
       (0, 2, 3),

       (1, 2, 6),
       (1, 4, 2),

       (2, 1, 2),
       (2, 3, 1),

       (3, 2, 2),
       (3, 4, 2);

Wykonanie:

$ GRAPH=graph-wikipedia.sql make
dropdb --if-exists bftest;
createdb bftest;
psql -1q bftest < schema.sql
psql -1q bftest < graph-wikipedia.sql
psql -1q bftest < bellman-ford.sql 
psql bftest -c "SELECT * FROM bellman_ford(0)"
 v | distance 
---+----------
 0 |        0
 1 |    5.000
 2 |    3.000
 3 |    4.000
 4 |    6.000
(5 rows)