ბელმან-ფორდი და უარყოფითი წიბოები

ზოგი წიბო ფულს გიბრუნებს: თანხის დაბრუნება, დაღმართი, რომელიც ელექტრომობილს ტენის, ვალუტის გაცვლა, რომელიც მოგებას იძლევა. ბელმან-ფორდი უარყოფით წონებს უმკლავდება და იმასაც გეტყვის, როცა „წრეზე ტრიალით“ ფასი უსასრულოდ ეცემა.

მოწინავე⏱ 12 წთ

←ეყრდნობა

8დეიქსტრას ალგორითმიბელმან-ფორდი დეიქსტრას რელაქსაციას იყენებს, ოღონდ ყველა წიბოზე იმეორებს, ამიტომ უარყოფითი წონებიც დასაშვებია.6გრაფის წარმოდგენაის უბრალოდ V − 1-ჯერ გადაუყვება წიბოთა სიას.

გზას უხსნის→

10ფლოიდ-ვორშელი: დპ გრაფზებელმან-ფორდის მსგავსად, ის რელაქსაციას მრავალჯერ იმეორებს და უარყოფით წონებსაც უძლებს.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ყველაფრის რელაქსაცია, ისევ და ისევ

დეიქსტრა უარყოფით წიბოებზე იმიტომ ცდება, რომ წვეროს ზედმეტად ადრე ნიშნავს საბოლოოდ. ბელმან-ფორდი ხარბ მონიშვნაზე საერთოდ უარს ამბობს: იყენებს იმავე რელაქსაციას, მაგრამ ყველა წიბოზე, ფიქსირებული რიგით, და მთელ გავლას იმეორებს.

რატომ მიდის ეს სწორ პასუხამდე? ავიღოთ ერთი უმოკლესი გზა s → a → b → c → d. პირველი გავლა აუცილებლად სწორად ამუშავებს s → a-ს; მეორე გავლა მერე a → b-ს, მესამე b → c-ს და ასე შემდეგ. k-ე რაუნდის შემდეგ სწორია ყველა უმოკლესი გზა, რომელიც არაუმეტეს k წიბოს იყენებს, მიუხედავად წიბოების რიგისა.

სინამდვილეში ეს დინამიური პროგრამირებაა წიბოების რაოდენობაზე, მე-10 ეტაპის წინასწარი გაცნობა.

02V − 1 რაუნდი საკმარისია

უარყოფითი ციკლების გარეშე უმოკლესი გზა წვეროს არ იმეორებს, ამიტომ მასში არაუმეტეს V − 1 წიბოა. ესე იგი V − 1 რაუნდი ყოველთვის საკმარისია:

d[s] = 0; გაიმეორე V−1-ჯერ: ყოველი წიბოსთვის (u, v, w): თუ d[u] + w < d[v]: d[v] = d[u] + w

ცხრილში ვიზუალიზატორის 5-წვეროიანი გრაფია. პირველ რაუნდში ყველა წვერო მიიღწევა; მეორეში იპოვება უფრო იაფი გზა წვერო 2-მდე −2 წიბოს გავლით; მესამე ამ გაუმჯობესებას წვერო 5-მდე (−2) ატარებს. მეოთხე რაუნდი არაფერს ცვლის.

ეს უფასო აჩქარებას იძლევა: თუ მთელმა რაუნდმა არაფერი შეცვალა, გავჩერდეთ. შემდეგაც არაფერი შეიცვლება. ბევრ რეალურ მონაცემზე ეს V − 1 რაუნდზე გაცილებით ადრე სრულდება.

მონიშნული უჯრები იმ რაუნდში შეიცვალა.

03უარყოფითი ციკლები: ერთი დამატებითი რაუნდი

თუ ციკლის ჯამური წონა უარყოფითია, მასზე რამდენჯერაც გინდა, იმდენჯერ შემოივლი და „მანძილს“ რამდენიც გინდა, იმდენად შეამცირებ: უმოკლესი გზა არ არსებობს.

ბელმან-ფორდი ამას უფასოდ აღმოაჩენს. V − 1 რაუნდის შემდეგ ყველა ნამდვილი უმოკლესი გზა საბოლოოა, ამიტომ გავუშვათ კიდევ ერთი რაუნდი. თუ რომელიმე წიბო ისევ აუმჯობესებს მანძილს, ერთადერთი ახსნაა საწყისი წვეროდან მისაღწევი უარყოფითი ციკლი.

ვიზუალიზატორში 4→3 წიბოს წონა −7-ზე დააყენე: ციკლი 3 → 2 → 4 → 3 მაშინ −2 + 8 − 7 = −1-ს იწონის და დამატებითი რაუნდი ამას აღმოაჩენს. კლასიკური გამოყენებაა ვალუტის არბიტრაჟი: წონებით −log(კურსი) უარყოფითი ციკლი გაცვლების ისეთი ჯაჭვია, რომელიც დაწყებულზე მეტი ფულით მთავრდება.

04ღირებულება და სწორი ინსტრუმენტის არჩევა

ყოველი რაუნდი ყველა E წიბოს ეხება, რაუნდები კი მაქსიმუმ V − 1-ია, პლუს შემოწმება: O(V·E) დრო და მხოლოდ O(V) დამატებითი მეხსიერება (მხოლოდ d[] და p[], წიბოები შეიძლება უბრალო სიაში იყოს). ეს დეიქსტრას O((V + E) log V)-ზე გაცილებით ნელია, ამიტომ გამოიყენე მხოლოდ მაშინ, როცა მისი შესაძლებლობები გჭირდება:

უარყოფითი წიბოები;
უარყოფითი ციკლების აღმოჩენა;
„არაუმეტეს k წიბო“ ტიპის კითხვები (გაჩერდი k რაუნდის შემდეგ და ყოველ რაუნდში d[]-ის ასლით იმუშავე).

რიგზე დაფუძნებული ვარიანტი (ხშირად SPFA-ს უწოდებენ) ხელახლა მხოლოდ იმ წვეროების წიბოებს ამუშავებს, რომლებიც ახლახან გაუმჯობესდა. პრაქტიკაში ხშირად სწრაფია, მაგრამ უარეს შემთხვევაში იგივე ღირს.

ფასი ერთი შეხედვით

დროO(V·E)

უარყოფითი ციკლის შემოწმებაO(E)

დამატებითი მეხსიერებაO(V)

დაიმახსოვრე

ბელმან-ფორდი ყველა წიბოს V − 1-ჯერ ამუშავებს; k-ე რაუნდის შემდეგ ≤ k წიბოიანი ყველა უმოკლესი გზა სწორია.
თუ დამატებითი რაუნდი კიდევ რამეს აუმჯობესებს, მისაღწევია უარყოფითი ციკლი და უმოკლესი გზა არ არსებობს.
ის O(V·E) ჯდება, ამიტომ როცა ყველა წონა არაუარყოფითია, დეიქსტრა ჯობია.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: დაითვალე გაუმჯობესებები თითო რაუნდში: ნულამდე მცირდება. მერე 4→3 დააყენე −7-ზე და ნახე, როგორ იჭერს დამატებითი რაუნდი უარყოფით ციკლს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ორიენტირებული წონადი გრაფი (საწყისი: 1) · რაუნდი 0

v	1	2	3	4	5
dist	0	∞	∞	∞	∞
parent	nil	nil	nil	nil	nil

ბელმან-ფორდი პოულობს უმოკლეს გზებს უარყოფითი წიბოებითაც, სადაც დეიქსტრას ხარბი მონიშვნა ტყდება. dist[1] = 0, ყველა სხვა ∞.

ფსევდოკოდი

 1 dist[s]=0, others ∞ 2 repeat |V|-1 times: 3   for every edge (u→v,w): if dist[u]+w < dist[v], relax it 4 one more pass: any relaxation now ⇒ a negative cycle

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

გრაფს 6 წვერო აქვს და უარყოფითი ციკლი არ აქვს. მაქსიმუმ რამდენი რაუნდი შეიძლება დასჭირდეს ბელმან-ფორდს?

№2

მესამე რაუნდი დასრულდა და არაფერი შეცვალა. რა ვიცით?

№3

გჭირდება უიაფესი მარშრუტი არაუმეტეს k ფრენით. რომელი ინსტრუმენტი ჯობია?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeNetwork Delay Time საშუალო↗LeetCodeCheapest Flights Within K Stops საშუალო↗CSESHigh Score მოწინავე↗CSESCycle Finding მოწინავე↗