Bellman Ford ալգորիթմն աշխատում է գերագնահատելով ճանապարհի երկարությունը մեկնարկային գագաթից մինչև մյուս բոլոր գագաթները: Այնուհետև այն պարբերաբար թուլացնում է այդ գնահատումները՝ գտնելով նոր ուղիներ, որոնք ավելի կարճ են, քան նախկինում գերագնահատված ուղիները:
Ինչու է աշխատում Bellman-Ford ալգորիթմը:
Bellman Ford ալգորիթմն աշխատում է գերագնահատելով ճանապարհի երկարությունը մեկնարկային գագաթից մինչև մյուս բոլոր գագաթները: Այնուհետև այն պարբերաբար թուլացնում է այդ գնահատումները՝ գտնելով նոր ուղիներ, որոնք ավելի կարճ են, քան նախկինում գերագնահատված ուղիները:
Բելման Ֆորդը միշտ աշխատում է:
Հեշտ է տեսնել, որ Բելման-Ֆորդի ալգորիթմը կարող է անվերջ թուլացնել այս ցիկլի բոլորգագաթները և նրանից հասանելի գագաթները:Հետևաբար, եթե փուլերի թիվը չսահմանափակեք n−1-ով, ապա ալգորիթմը կաշխատի անորոշ ժամանակով՝ անընդհատ բարելավելով այս գագաթներից հեռավորությունը:
Ինչու է Bellman Ford-ը վազում N 1 անգամ:
Այն, ինչ մենք անում ենք BellmanFord-ում, մենք հանգստացնում ենք ճանապարհի երկարության եզրերը 1, այնուհետև հաջորդ անգամ մենք թուլացնում ենք 2-րդ երկարության արահետների եզրերը ……այդպես շարունակ, մինչև հանգստացնենք ճանապարհի եզրերը: երկարությունը n-1. Հետևաբար հանգույցն աշխատում է n-1 անգամ։
Բելման Ֆորդը ագահ ալգորիթմ է:
Bellman Ford-ի ալգորիթմն աշխատում է, երբ կա բացասական քաշի եզր, այն նաև հայտնաբերում է քաշի բացասական ցիկլը: Dijkstra-ի ալգորիթմը չի աշխատում, երբ կա բացասական քաշի եզր: … Ալգորիթմի իրականացման համար կիրառվում է դինամիկ ծրագրավորման մոտեցում: Ագահական մոտեցում է կիրառվում ալգորիթմն իրականացնելու համար:
