Difference between revisions 1395182 and 1431643 on hywiki

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

(contracted; show full)
 ''// This implementation takes in a graph, represented as lists of vertices''
 ''// and edges, and modifies the vertices so that their ''distance'' and''
 ''//'' predecessor ''attributes store the shortest paths.''

 ''// Step 1: initialize graph''
 '''for each''' vertex v '''in''' vertices:

   '''if''' v '''is''' source '''then''' v.distance := 0
   '''else''' v.distance := '''infinity'''
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.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ։

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