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

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

Алгоритам 

Као и Дејкстрин алгоритам, Белман-Фордов је основан на принципу итеративне методе по имену релаксација, у коме се апроксимација тачне удаљености постепено смењује тачнијом вредношћу све док се евентуално не достигне оптимално решење. У оба алгоритма, приближна удаљеност до сваког чвора је увек прецењена вредност тачне удаљености, и замењује се минимумом своје старе вредности и дужине новооткривеног пута.
Међутим, Дејкстрин алгоритам похлепно бира чвор са најмањом тежином који још увек није посећен, и понавља исти поступак на свим осталим ивицама; у поређењу, Белман-Фордов алгоритам једноставно релаксира све ивице, и то чини |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

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

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

Примена у рутирању 

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

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

Унапређења 
Белман-Фордов алгоритам се може унапредити у пракси (али не и у најгорем случају) уз посматрање да, уколико се итерација главне петље алгоритма терминира без прављења неких промена, алгоритам се може истог тренутка терминира, зато што наредне итерације неће правити измене. Уз овај услов, главна петља у неким случајевима има много мање од |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.

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

Референце

Литература

Оригинални извори

Секундарни извори 
 
 Introduction to Algorithms, Second Edition. .. Section 24.1: The Bellman–Ford algorithm, pp. 588-592. Problem 24-1, pp. 614-615. Third Edition. . Section 24.1: The Bellman–Ford algorithm, pp. 651-655.

Спољашње везе 

 Open Source Java пакет за рад са графовима и Белман-Фордовим алгоритмом

Графовски алгоритми
Динамичко програмирање
Белман-Фордов алгоритам је алгоритам који рачуна најкраћи пут из једног ка свим другим чворовима у тежинском диграфу . Спорији је од Дејкстриног алгоритма , али је прилагодљивији , зато што може да ради и са графовима чије су неке ивице негативних тежина . Алгоритам је именован по своја два развијаоца , Ричарду Белману и Лестеру Форду Млађем , који су га објавили и ; међутим , Едвард Ф . Мур је такође објавио исти алгоритам због чега се алгоритам понекад назива Белман-Форд-Муров алгоритам . Ивице са негативним тежинама се могу наћи у многим применама графова , што чини овај алгоритам веома корисним . Међутим , ако граф садржи " негативни циклус " , нпр . , циклус чије ивице имају негативни збир , онда нема најјефтинијег пута , зато што у том случају сваки пут може постати јефтинији ако се још једном прође кроз негативни циклус . У таквим случајевима , Белман-Фордов алгоритам може открити негативне циклусе и пријавити њихово постојање , али не може произвести тачан најкраћи пут уколико се до негативног циклуса може доћи из почетног чвора . Алгоритам Као и Дејкстрин алгоритам , Белман-Фордов је основан на принципу итеративне методе по имену релаксација , у коме се апроксимација тачне удаљености постепено смењује тачнијом вредношћу све док се евентуално не достигне оптимално решење . У оба алгоритма , приближна удаљеност до сваког чвора је увек прецењена вредност тачне удаљености , и замењује се минимумом своје старе вредности и дужине новооткривеног пута . Међутим , Дејкстрин алгоритам похлепно бира чвор са најмањом тежином који још увек није посећен , и понавља исти поступак на свим осталим ивицама ; у поређењу , Белман-Фордов алгоритам једноставно релаксира све ивице , и то чини |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 Inicijalizacija grafa for each vertex v in vertices : if v is source then distance[ v ] \ := 0 else distance[ v ] \ := infinity predecessor[ v ] \ := null / / Korak Ponovljena relaksacija ivica for i fromto 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 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 =и тренутак пре него што је for петља покренута по први пут . У том случају је , за почетни чвор , source.distance = што је тачно . За остале чворове u важи u.distance = infinity , што је такође тачно , зато што не постоји пут из source до u сачињен одивица . У индуктивном кораку , прво доказујемо први корак . Разматрајмо тренутак када се удаљеност чвора мења са 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 fromto k of v[ i-1 ( mod k ) ]v[ i ] .weight То јест , сваки циклус има ненегативну вредност . Налажење негативних циклуса Када се алгоритам користи за претрагу најкраћег пута , постојање негативних циклуса је проблем који спречава алгоритам да пронађе тачан одговор . Међутим , с обзиром да стаје када наиђе на негативни циклус , Белман-Фордов алгоритам се може користити у апликацијама у којој је то циљ - на пример у техникама поништавања циклуса у анализи транспортационих мрежа . Примена у рутирању Дистрибуирана варијанта Белман-Фордовог алгоритма се користи у протоколима рутирања на основу вектора удаљености , на пример , у RIP-у . Алгоритам је дистрибуиран зато што укључује неки број чворова ( рутера ) унутар аутономног система , скупа IP мрежа које су углавном у власништву неког ISP-а . Састоји се из следећих корака : Сваки чвор рачуна растојање између себе и свих других чворова унутар AS-а и складишти ову информацију унутар табеле . Сваки чвор шаље своју табелу суседним чворовима . Када чвор прими табелу од својис суседа , он израчунава најкраћу путању до свих других чворова и мења своју табелу уколико је дошло до неких промена . Главне мане Белман-Фордовог алгоритма у овом окружењу су : Скалирање се не врши добро . Промене у топологији мреже се не одражавају брзо , пошто се исправке шире са чвора на чвор . Проблем бројења до бесконачности ( уколико услед неке грешке дође до тога да је неки чвор недостижан из неког скупа других чворова , ти чворови могу да повећавају своје процене растојања до недостижног чвора ) . Унапређења Белман-Фордов алгоритам се може унапредити у пракси ( али не и у најгорем случају ) уз посматрање да , уколико се итерација главне петље алгоритма терминира без прављења неких промена , алгоритам се може истог тренутка терминира , зато што наредне итерације неће правити измене . Уз овај услов , главна петља у неким случајевима има много мање од |V| − 1 итерација , иако најгори случај алгоритма остаје непромењен . Јенописује још два унапређења Белман-Фордовог алгоритма за граф без циклуса негативне тежине ; опет , иако чине алгоритам бржи у пракси , не мењају његов најгори случај од 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. Још једно унапређење од стране Банистера и Епштајна замењује арбитрарни линеарни ред чворова коришћених у Јеновом другом унапређењу са насумичном пермутацијом . Ова промена чини да се најгори случај за Јеново унапређење ( у коме чворови најкраћег пута стриктно алтернирају између два подскупа Ef и Eb ) веома тешко догоди . Са насумичном пермутацијом редоследа чворова , очекивана вредност за број итерација потребних у главној петњи је највише |V| / 3. Референце Литература Оригинални извори Секундарни извори Introduction to Algorithms , Second Edition . \ .. Section1 : The Bellman–Ford algorithm , pp . Problem pp . Third Edition . \ . Section1 : The Bellman–Ford algorithm , pp . Спољашње везе Open Source Java пакет за рад са графовима и Белман-Фордовим алгоритмом Графовски алгоритми Динамичко програмирање