Белман-Фордов алгоритам

Белман-Фордовиот алгоритам е алгоритам кој ги пресметува најкратките патеки од едно изворно теме во насочен тежински граф. Името на овој алгоритам доаѓа од Ричард Белман и Лестер Форд, кои први го објавиле во научни трудови во 1958, односно 1956 година, но овој алгоритам првпат бил предложен како решение уште во 1955 од Алфонсо Шимбел. Предноста на Белман-Фордовиот алгоритам наспроти класичните алгоритми за барање најкратки патеки како алгоритмот на Дајкстра е дека може да работи со графови кои имаат ребра со негативни тежини.

Белман-Фордов алгоритам

Класа	Пребарувачки алгоритам
Структура на податоци	Граф
Најлош случај	$\Theta (|V||E|)$
Најдобар случај	$\Theta (|E|)$
Просторна сложеност во најлош случај	$\Theta (|V|)$

Функционирање на алгоритмот

За разлика од алгоритмот на Дајкстра, каде се бележи кое теме веќе посетено, во алгоритмот на Белман-Форд само се бележи растојанието кон сите темиња од изворот. Ова се прави бидејќи темињата се посетуваат повеќепати (заради дозволените негативни тежини).

Нека $D(u)$ е од изворот I до некое теме u во даден граф, $(u,v)$ е ребро од теме u до v од графот, и $W(u,v)$ е тежина на реброто $(u,v)$. На почеток, $D(I)$ е 0, бидејќи растојанието од изворот до изворот е нула. Сите останати темиња добиваат $D(u)=\infty$, бидејќи нема патека без темиња кон нив.

Потоа, за сите $(u,v)$, се проверува дали $D(u)+W(u,v)$ е помало од $D(v)$, и го променуваме $D(v)$ доколку е, соодветно. Со една ваква итерација на сите ребра алгоритмот не би го открил најкраткиот пат, бидејќи не ги проверува сите можни патеки. Како решение на овој проблем, алгоритмот се извршува |V|-1 пати, каде V e бројот на темиња. Временската комплексност на овој алгоритам е $O(|V|*|E|)$, каде $|E|$ е бројот на ребра во графот.

Имплементација

Пример за типична имплементација на овој алгоритам во програмскиот јазик Пајтон 3, без проверка за постоење на негативни циклуси во графот:

import math
def BelmanFord(teminja, rebra, izvor):
    # D[u] е оддалеченост од извор до u
    D = {}
    # prethodnik[u] e претходното најкратко теме до u
    prethodnik = {}
    for teme in teminja:
        D[teme] = math.inf
        prethodnik[teme] = None
    # Оддалеченост од извор до извор е секогаш нула
    D[izvor] = 0
    for i in range(len(teminja) - 1):
        for (u, v, w) in rebra:
            if D[u] + w < D[v]:
                D[v] = D[u] + w
                prethodnik[v] = u
    return (D, prethodnik)

Пример со конкретен граф

На сликата е прикажан насочен тежински граф со четири темиња кој содржи негативни тежини, и проблемот е да се пронајде најкратката патека од Тања до Филип:

Со повикување на претходно дефинираната функција со изворно теме Тања, добиваме подреден пар $(D,P)$ кој содржи најкраток пат од Тања до сите темиња, каде $D(u)$ е должината на патеката кон $u$ како број, а $P(u)$ е претходното оптимално теме на $u$.

# Со Белман Форд ги бараме најкратките патеки од Тања
D, P = BelmanFord(graf1_teminja, graf1_rebra, 'Тања')
print('Должина на најкраток пат од Тања до Филип: ')
print(D['Филип'])
# Темиња на најкраткиот пат од Тања до Филип
teme = 'Филип'
print('Темиња почнувајќи од Филип:')
while teme is not None:
    # Го печатиме моменталното теме teme
    print(teme)
    # Го поставуваме за моментално претходното оптимално теме (P[teme])
    teme = P[teme]

Должина на најкраток пат од Тања до Филип: 
0
Темиња почнувајќи од Филип:
Филип
Дарко
Мила
Тања

Доказ

Доказот дека овој алгоритам го наоѓа оптималното решение може да се реализира со математичка индукција. Лема. После $i$ повторувања на for-циклусот:

• Ако $D(u)$ не е $\infty$, тогаш е еднакво на должината на некоја патека од $s$ до $u$ (каде $D$ е функцијата за оддалеченост)
• Ако има патека од $s$ до $u$ со највеќе $i$ ребра, тогаш $D(u)$ е помало или еднакво на должината на најкратката патека од $s$ до $u$ со највеќе $i$ ребра.

Основен случај. Кога $i=0$, потребна е патека од изворното теме до останатите темиња u, но патеката треба да има 0 ребра. Бидејќи $D(I)=0$ (растојанието од изворот до изворот е 0), а за сите останати темиња u, $D(u)=\infty$ (што е точно бидејќи нема патека кон u со 0 ребра), условот е задоволен.

Индуктивен случај. Кога некое теме има променета оддалеченост од изворот, се извршува $D(v)=D(u)+W(u,v)$ каде $W(u,v)$ е тежината на реброто $(u,v)$. Од индуктивната претпоставка, $D(u)$ е должината на некоја патека од изворот до $u$. Тогаш $D(u)+W(u,v)$ е должината на патеката од изворот до $v$ (што оди од изворот I до $u$, и потоа $v$).

Да претпоставиме дека $P$ е најкратката патека (може да постојат повеќе) од извор до $u$ со највеќе $i$ темиња. Нека $v$ е темето пред u во патеката $P$. Тогаш, најкратката патека од изворот до $v$ со највеќе $i-1$ темиња ќе е делот од патеката од изворот до $u$ без $u$. Од индуктивната претпоставка, $D(v)$ после $i-1$ повторувања е највеќе должината на таа патека од изворот до $v$. Затоа, $W(u,v)+D(v)$ е највеќе должината на $P$. Во $i$-тата итерација, се споредува $D(u)$ со $W(u,v)+D(v)$ и се променува вредноста на $D(u)$ доколку претходниот израз е помал. Така, после $i$ итерации, $D(u)$ e највеќе должината на $P$, односно должината на најкратката патека од изворот кон $u$.

Поврзано

• Теорија на графови
• Алгоритам на Дајкстра
• Примов Алгоритам

Надворешни врски

• Александар Андевски - Најкраток пат во граф со негативни тежини