Difference between revisions 1431643 and 1438485 on hywiki

''Bellman – Ford ալգորիթմ''-ը հաշվարկում է միաղբյուր [[ամենակարճ ճանապարհ]]ները [[կշռավոր արտահայտություն]]ներում: Միայն ոչ բացասական եզրին կշիռներով ալգորիթմերի համար, ավելի արագ [[Dijkstra ալգորիթմ]]ը նույնպես լուծում է խնդիրը։
Այսպիսով, Bellman – Ford-ը օգտագործվում է հիմնականում բացասական եզրային կշիռներով գրաֆիկների համր։ Ալգորիթմն իր անունը ստացել է իր մշակողների, [[Ռիչարդ Բելլման]]ի և [[Լեստեր Ֆորդ կրտ.]]ի անուններից։

Եթե գրաֆիկի պարունակում է “բացասական ցիկլ”, այսինքն, [[ցիկլ]], որի եզրերի գումարը բացասական արժեք է, ապա, կամայականորեն ցածր կշռի [[անցում]]ները կարող են կառուցվել, այսինքն, չի կարող լինել ինչ-որ “ամենակարճ” ճանապարհ։ Bellman – Ford-ը կարող է հայտնաբերել բացասական ցիկլերը և հաղորդել դրանց գոյությունը, բայց այն չի կարող արտադրել ճիշտ պատասխան, եթե բացասական ցիկլը հասանելի չէ աղբյուրից։

Ըստ [[Ռոբերտ Սեդջուիք]]ի, «Բացասական կշիռները պարզապես մաթեմատիկական հետաքրքրություն չեն,   դրանք առաջանում են բնական ձևով, երբ մենք կրճատում ենք այլ խնդիրները ամենակարճ ճանապարհներով խնդիրների»: Ենթադրենք “G” գրաֆիկ է, որը պարունակում է բացասական ցիկլ։ Ամենակարճ ճանապարհով խնդրի մեկ [[NP-ամբողջական]] տարբերակը, պահանջում է ամենակարճ ամենակարճ ճանապարհ “G”-ում (պարունակում է բացասական ցիկլը), այնպես որ ոչ մի եզր չկրկնվի։ Սեդջուիքը տալիս է [[Համիլտոնյան ճանապարհի խնդրի]] [[կրճատում]] մինչև խնդրի այս տարբերակը։

=Ալգորիթմ=
(contracted; show full)
v.predecessor := '''null'''

 ''// Step 2: relax edges repeatedly''
 '''for''' i '''from''' 1 '''to''' size(vertices), 1:
 '''for each''' edge uv '''in''' edges: ''// uv is the edge from u to v''
u := uv.source
v := uv.destination

   '''if''' u.distance + uv.weight < v.distance:
v.distance := u.distance + uv.weight
v.predecessor := u

 ''// Step 3: check for negative-weight cycles''
 '''for each''' edge uv '''in''' edges:
u := uv.source
v := uv.destination
 '''if''' u.distance + uv.weight < v.distance:
   '''error''' "Graph contains a negative-weight cycle"

=Ճշտության ապացույց=
Ալգրիթմի ճշությունը կարելի ե ցույց տալ [[մաթեմատիկական ինդուկցիա]]յի միիջոցով։ Ահա ինդուկցիայով ցուցադրված կոկնկրետ արտահայություն,

«Լեմ»: «for» ցիկլի «i» կրկնություններ.
*Եթե տարածություն(«u») անվերջություն չէ, այն հավասար է «s»ից դեպի «u» որոշ ճանապարհների երկարությունը։
(contracted; show full)3.	Երբ հանգույցը ստանում է իր հարևանի գրաֆիկը, այն հաշվում էամենակարճ ճանապարհները մյուս հանգույցների համեմատ և համապատասխանաբար թարմացնում իր սեփական գրաֆիկը։

Bellman–Ford ալգորիթմի հիմնական թերություններն են`
1.	Այն լավ չի հաշվարկում կշիռը։
2.	Փոփոխությունները [[ցանցային տոպոլոգիա]]ում արագ չեն երևում, քանզի թարմացումները փոխանցվում են հանգույցից հանգույց։
3.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ։

[[Կատեգորիա:Ալգորիթմներ]]