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

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето
Белман-Фордов алгоритам
КласаПребарувачки алгоритам
Структура на податоциГраф
Најлош случај
Најдобар случај
Просторна сложеност во најлош случај

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

Функционирање на алгоритмот[уреди | уреди извор]

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

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

Потоа, за сите , се проверува дали е помало од , и го променуваме доколку е, соодветно. Со една ваква итерација на сите ребра алгоритмот не би го открил најкраткиот пат, бидејќи не ги проверува сите можни патеки. Како решение на овој проблем, алгоритмот се извршува |V|-1 пати, каде V e бројот на темиња.[3]Временската комплексност на овој алгоритам е , каде е бројот на ребра во графот.

Имплементација[уреди | уреди извор]

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

 1 import math
 2 def BelmanFord(teminja, rebra, izvor):
 3     # D[u] е оддалеченост од извор до u
 4     D = {}
 5     # prethodnik[u] e претходното најкратко теме до u
 6     prethodnik = {}
 7     for teme in teminja:
 8         D[teme] = math.inf
 9         prethodnik[teme] = None
10     # Оддалеченост од извор до извор е секогаш нула
11     D[izvor] = 0
12     for i in range(len(teminja) - 1):
13         for (u, v, w) in rebra:
14             if D[u] + w < D[v]:
15                 D[v] = D[u] + w
16                 prethodnik[v] = u
17     return (D, prethodnik)

Пример со конкретен граф[уреди | уреди извор]

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

Пример за тежински граф.png

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

 1 # Со Белман Форд ги бараме најкратките патеки од Тања
 2 D, P = BelmanFord(graf1_teminja, graf1_rebra, 'Тања')
 3 print('Должина на најкраток пат од Тања до Филип: ')
 4 print(D['Филип'])
 5 # Темиња на најкраткиот пат од Тања до Филип
 6 teme = 'Филип'
 7 print('Темиња почнувајќи од Филип:')
 8 while teme is not None:
 9     # Го печатиме моменталното теме teme
10     print(teme)
11     # Го поставуваме за моментално претходното оптимално теме (P[teme])
12     teme = P[teme]
Должина на најкраток пат од Тања до Филип: 
0
Темиња почнувајќи од Филип:
Филип
Дарко
Мила
Тања


Доказ[уреди | уреди извор]

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

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

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

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

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

Поврзано[уреди | уреди извор]

Наводи[уреди | уреди извор]

  1. Bang-Jensen & Gutin (2000)
  2. Schrijver (2005)
  3. "Најкраток пат во граф со негативни тежини", Александар Андевски. Пристапено на: 08 февруари 2018.

Надворешни врски[уреди | уреди извор]