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)