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

{{Infobox algorithm
|class=[[Пребарувачки алгоритам]]
|image=
|caption = 
|data=[[Граф]]
|time=<math>\Theta (|V| |E|)</math>
|best-time=<math>\Theta (|E|)</math>
|space=<math>\Theta (|V|)</math>
}}
'''Белман-Фордовиот алгоритам''' е [[алгоритам]] кој ги пресметува најкратките патеки од едно изворно теме во насочен тежински [[граф]].<ref name=Bang>{{harvtxt|Bang-Jensen|Gutin|2000}}</ref> Името на овој алгоритам доаѓа од Ричард Белман и Лестер Форд, кои први го објавиле во научни трудови во 1958, односно 1956 година<ref name="Schrijver">{{harvtxt|Schrijver|2005}}</ref>, но овој алгоритам првпат бил предложен како решение уште во 1955 од Алфонсо Шимбел. Предноста на Белман-Фордовиот алгоритам наспроти класичните алгоритми за барање најкратки патеки како [[Дајкстрин алгоритам|Дајкстриниот алгоритам]] е дека може да работи со графови кои имаат ребра со негативни тежини.

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

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

Потоа, за сите <math>(u, v)</math>, се проверува дали <math>D(u) + W(u, v)</math> е помало од <math>D(v)</math>, и го променуваме <math>D(v)</math> доколку е, соодветно. Со една ваква итерација на сите ребра алгоритмот не би го открил најкраткиот пат, бидејќи не ги проверува сите можни патеки. Како решение на овој проблем, алгоритмот се извршува |V|-1 пати, каде V e бројот на темиња.<ref>[https://aandevski.wordpress.com/2015/07/25/%D0%BD%D0%B0%D1%98%D0%BA%D1%80%D0%B0%D1%82%D0%BE%D0%BA-%D0%BF%D0%B0%D1%82-%D0%B2%D0%BE-%D0%B3%D1%80%D0%B0%D1%84-%D1%81%D0%BE-%D0%BD%D0%B5%D0%B3%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B8-%D1%82%D0%B5%D0%B6/  "Најкраток пат во граф со негативни тежини"], Александар Андевски. Пристапено на: 8 февруари 2018.</ref> Временската комплексност на овој алгоритам е <math>O(|V| * |E|)</math>, каде <math>|E|</math> е бројот на ребра во графот.

=== Имплементација ===
Пример за типична имплементација на овој алгоритам во програмскиот јазик [[Пајтон (програмски јазик)|Пајтон 3]], без проверка за постоење на негативни циклуси во графот: 
<syntaxhighlight lang="python" line='line'>
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)
</syntaxhighlight>
=== Пример со конкретен граф ===
На сликата е прикажан насочен тежински граф со четири темиња кој содржи негативни тежини, и проблемот е да се пронајде најкратката патека од Тања до Филип:

[[Податотека:Пример за тежински граф.png|center]]

Со повикување на претходно дефинираната функција со изворно теме Тања, добиваме подреден пар <math>(D, P)</math> кој содржи најкраток пат од Тања до сите темиња, каде <math>D(u)</math> е должината на патеката кон <math>u</math> како број, а <math>P(u)</math> е претходното оптимално теме на <math>u</math>.
<syntaxhighlight lang="python" line='line'>
# Со Белман Форд ги бараме најкратките патеки од Тања
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]
</syntaxhighlight>
<syntaxhighlight>
Должина на најкраток пат од Тања до Филип: 
0
Темиња почнувајќи од Филип:
Филип
Дарко
Мила
Тања
</syntaxhighlight>

== Доказ ==

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

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

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

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

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

== Поврзано ==
* [[Теорија на графови]]
* [[Дајкстрин алгоритам]]
* [[Примов алгоритам]]
== Наводи ==
{{наводи}}

== Надворешни врски ==
* [https://aandevski.wordpress.com/2015/07/25/%D0%BD%D0%B0%D1%98%D0%BA%D1%80%D0%B0%D1%82%D0%BE%D0%BA-%D0%BF%D0%B0%D1%82-%D0%B2%D0%BE-%D0%B3%D1%80%D0%B0%D1%84-%D1%81%D0%BE-%D0%BD%D0%B5%D0%B3%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B8-%D1%82%D0%B5%D0%B6/ Александар Андевски - Најкраток пат во граф со негативни тежини]

[[Категорија:Алгоритми]]