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

Из Википедије, слободне енциклопедије
Белман-Фордов алгоритам
Намена Налажење најкраћег пута (за усмерене тежинске графове)
Структура података Граф
Временска компл. O (|V| |E|)
Меморијска компл. O (|V|)

Белман-Фордов алгоритам је алгоритам који рачуна најкраћи пут из једног ка свим другим чворовима у тежинском диграфу.[1] Спорији је од Дејкстриног алгоритма, али је прилагодљивији, зато што може да ради и са графовима чије су неке ивице негативних тежина. Алгоритам је именован по своја два развијаоца, Ричарду Белману и Лестеру Форду Млађем, који су га објавили 1958. и 1956.; међутим, Едвард Ф. Мур је такође објавио исти алгоритам 1957., због чега се алгоритам понекада назива Белман-Форд-Муров алгоритам.[1]

Ивице са негативним тежинама се могу наћи у многим применама графова, што чини овај алгоритам веома корисним.[2] Међутим, ако граф садржи "негативни цикл", нпр., цикл чије ивице имају негативни збир, онда нема најјефтинијег пута, зато што у том случају сваки пут може постати јефтинији ако се још једном прође кроз негативни цикл. У таквим случајевима, Белман-Фордов алгоритам може открити негативне цикле и пријавити њихово постојање, али не може произвести тачан најкраћи пут уколико се до негативног цикла може доћи из почетног чвора.[3][1]

Алгоритам[уреди]

У овом примеру, под претпоставком да је А почетни чвор и да се ивице обилазе у најгорем могућем поредку, с десна у лево, потребно је пуних |V|−1 или 4 итерација како би процене даљине конвергирале. Насупрот томе, ако су ивице обрађене у најбољем могућем редоследу, с лева у десно, алгоритам конвергира у једну итерацију.

Као и Дејкстрин алгоритам, Белман-Фордов је основан на принципу итеративне методе по имену релаксација, у коме се апроксимација тачне удаљености постепено смењује тачнијом вредношћу све док се евентуално не достигне оптимално решење. У оба алгоритма, приближна удаљеност до сваког чвора је увек прецењена вредност тачне удаљености, и замењује се минимумом своје старе вредности и дужине новооткривеног пута. Међутим, Дејкстрин алгоритам похлепно бира чвор са најмањом тежином који још увек није посећен, и понавља исти поступак на свим осталим ивицама; у поређењу, Белман-Фордов алгоритам једноставно релаксира све ивице, и то чини |V | − 1 пута, где је |V | број чворова у графу. У сваком новом понављању, број чворова са тачно израчунатом удаљености расте, одакле следи да ће евентуално сви чворови имати тачно израчунате удаљености. Ова метода допушта Белман-Фордовом алгоритму да се користи на ширу класу улаза од Дејкстриног.

Белман-Форд се извршава у времену O(|V|·|E|), где су |V| и |E| бројеви чворова и ивица.

procedure BellmanFord(list vertices, list edges, vertex source)
   // Ova implementacija prima graf, predstavljen kao lista čvorova – vertices,
   // i ivica - edges, i popunjava dva niza (udaljenost – distance,
   // prijethodnik – predecessor) informacijama o najkraćem putu

   // Korak 1: Inicijalizacija grafa
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Korak 2: Ponovljena relaksacija ivica
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Korak 3: Provjera da li postoje ciklusi sa negativnom težinom
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"

Доказ коректности[уреди]

Коректност алгоритма се може показати математичком индукцијом.

Лема. Након i понављања for петље:

  • Ако Distance(u) није бесконачно, онда је једнако дужини путање од s до u;
  • Ако постоји пут од s до u са највише i ивица, онда Distance(u) није веће од дужине најкраћег пута од s до u са највише i ивица.

Доказ. За базни случај индукције, разматрајмо i = 0 и тренутак пре него што је for петља покренута по први пут. У том случају је, за почетни чвор, source.distance = 0, што је тачно. За остале чворове u важи u.distance = infinity, што је такође тачно, зато што не постоји пут из source до u сачињен од 0 ивица.

У индуктивном кораку, прво доказујемо први корак. Разматрајмо тренутак када се удаљеност чвора мења са v.distance := u.distance + uv.weight. По индуктивној хипотези, u.distance је дужина неког пута од source до u. онда је u.distance + uv.weight дужина пута од source до v која прати пут од source до u а онда иде до v.

Што се тиче другог корака, разматрајмо најкраћи пут од source до u са највише i ивица. Нека је v чвор пре u на овом путу. Онда, део пута од source до v је најкраћи пут од source до v са највише i-1 ивица. По индуктивној хипотези, v.distance после i−1 итерација петље није већа од дужине овог пута. Одатле следи да uv.weight + v.distance није већа од дужине пута од s до u. У i-toj итерацији, u.distance се пореди са uv.weight + v.distance, и једнака јој је уколико је uv.weight + v.distance било мање. Дакле, после i итерација, u.distance није веће од дужине најкраћег пута од source до u са највише i ивица.

Уколико нема цикла са негативном тежином, онда сваки најкраћи пут посети сваки чвор највише једном, тако да се у трећем кораку не може направити неко побољшање. Насупрот томе, претпоставимо да се не може направити побољшање. онда за сваки цикл са чворовима v[0], ..., v[k−1] важи,

v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight

Сумирањем око цикла, v[i].distance и v[i−1 (mod k)] distance се потиру, остављајући 0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

То јест, сваки цикл има ненегативну вредност.

Налажење негативних циклова[уреди]

Када се алгоритам користи за претрагу најкраћег пута, постојање негативних цикла је проблем који спречава алгоритам да пронађе тачан одговор. Међутим, с обзиром да стаје када наиђе на негативни цикл, Белман-Фордов алгоритам се може користити у апликацијама у којој је то циљ - на пример у техникама поништавања цикла у анализи транспортационих мрежа.[1]

Примена у рутирању[уреди]

Дистрибуирана варијанта Белман-Фордовог алгоритма се користи у протоколима рутирања на основу вектора удаљености, на пример, у RIP-у. Алгоритам је дистрибуиран зато што укључује неки број чворова (рутера) унутар аутономног система, скупа IP мрежа које су углавном у власништву неког ISP-а. Састоји се из следећих корака:

  1. Сваки чвор рачуна растојање између себе и свих других чворова унутар AS-а и складишти ову информацију унутар табеле.
  2. Сваки чвор шаље своју табелу суседним чворовима.
  3. Када чвор прими табелу од својис суседа, он израчунава најкраћу путању до свих других чворова и мења своју табелу уколико је дошло до неких промена.

Главне мане Белман-Фордовог алгоритма у овом окружењу су:

  • Скалирање се не врши добро.
  • Промене у топологији мреже се не одражавају брзо, пошто се исправке шире са чвора на чвор.
  • Проблем бројења до бесконачности (уколико услед неке грешке дође до тога да је неки чвор недостижан из неког скупа других чворова, ти чворови могу да повећавају своје процене растојања до недостижног чвора).

Унапређења[уреди]

Белман-Фордов алгоритам се може унапредити у пракси (али не и у најгорем случају) уз посматрање да, уколико се итерација главне петље алгоритма терминира без прављења неких промена, алгоритам се може истог тренутка терминира, зато што наредне итерације неће правити измене. Уз овај услов, главна петља у неким случајевима има много мање од |V| − 1 итерација, иако најгори случај алгоритма остаје непромењен.

Јен (1970) описује још два унапређења Белман-Фордовог алгоритма за граф без цикла негативне тежине; опет, иако чине алгоритам бржи у пракси, не мењају његов најгори случај од O(|V|*|E|). Његово прво унапређење смањује број релаксационих корака који су потребни за сваку итерацију алгоритма. Ако чвор v има удаљеност која се није променила од последњег пута када су се ивице које иду из v релаксирале, онда нема потребе релаксирати ивице из v по други пут. На овај начин, како се број чворова са тачним удаљеностима повећава, број ивица које требају да се релаксирају у свакој итерацији смањује, што води до константног уштеђења времена за густе графове.

Јеново друго унапређење прво додељује арбитрарни линеарни ред свим чворовима и онда партиционише скуп свих чворова на два подскупова. Први подскуп, Ef, садржи све ивице (vi, vj) такве да је i < j; други подскуп, Eb, садржи ивице (vi, vj) такве да је i > j. Сваки чвор је посећен редом v1, v2, ..., v|V|, релаксирајући сваку ивицу која иде од тог чвора из Ef. Сваки чвор се онда посећује редом v|V|, v|V|−1, ..., v1, релаксирајући сваку ивицу која иде из чвора Eb. Свака итерација у главној петљи алгоритма, после прве, додаје барем две ивице у скуп ивица чије се релаксиране удаљености поклапају са тачним најкраћим путем: једна из Ef и једна из Eb. Ова модификација смањује број итерација главне петље у најгорем случају са |V| − 1 на |V|/2.[4][5]

Још једно унапређење од стране Банистера и Епштајна (2012), замењује арбитрарни линеарни ред чворова коришћених у Јеновом другом унапређењу са насумичном пермутацијом. Ова промена чини да се најгори случај за Јеново унапређење (у коме чворови најкраћег пута стриктно алтернирају између два подскупа Ef и Eb) веома тешко догоди. Са насумичном пермутацијом редоследа чворова, очекивана вредност за број итерација потребних у главној петњи је највише |V|/3.[5]

Референце[уреди]

  1. ^ а б в г Bang-Jensen & Gutin (2000)
  2. ^ Sedgewick (2002)
  3. ^ Kleinberg & Tardos (2006)
  4. ^ Cormen et al., 2nd ed., Problem 24-1, pp. 614–615.
  5. ^ а б Погледајте Сеџвикова вежбања под Algorithms, 4th ed., вежбања 5 и 11 (преузето 2013-01-30).

Литература[уреди]

Оригинални извори[уреди]

  • Bellman, Richard (1958). „On a routing problem“. Quarterly of Applied Mathematics 16: 87–90. MR 0102435. 
  • Ford Jr., Lester R. (1956). Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation. 
  • Moore, Edward F. (1959). „The shortest path through a maze“. Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Mass.: Harvard Univ. Press. pp. 285–292. MR 0114710. 
  • Yen, Jin Y. (1970). „An algorithm for finding shortest routes from all source nodes to a given destination in general networks“. Quarterly of Applied Mathematics 27: 526–530. MR 0253822. 
  • Bannister, M. J.; Eppstein, D. (2012). „Randomized speedup of the Bellman–Ford algorithm“. Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan. pp. 41–47. arXiv:1111.5414. 

Секундарни извори[уреди]

Спољашње везе[уреди]