Difference between revisions 1389176 and 1395182 on hywiki

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

(contracted; show full)

Bellman - Ford ներմուծում է “[[Մեծ O նշում]]” (|“V”| • |“E”|) ժամանակահատված, որտեղ |“V”|-ն ու |“E”|-ն համապատասխանաբար անկյունների և եզրերի քանակներն են։

 '''procedure''' BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source)

   ''// 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.	[[Մինչև անվերջություն հաշվել]]ու խնդիրներ։

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