ფლოიდ-ვორშელი: დპ გრაფზე

დეიქსტრა მანძილებს ერთი წყაროდან იძლევა. ყველა წყვილისთვის მისი V-ჯერ გაშვება შეიძლებოდა, მაგრამ უარყოფითი წიბოებით ის ცდება, ბელმან-ფორდის V-ჯერ გაშვება კი O(V²E) ღირს.

ფლოიდ-ვორშელი მუშაობს მანძილების მატრიცაზე d[i][j]: ვიწყებთ წიბოს წონით იქ, სადაც წიბო არსებობს, დიაგონალზე 0-ით და სხვაგან ∞-ით. დასრულებისას d[i][j] უმოკლესი მანძილია i-დან j-მდე ყველა წყვილისთვის. ის უარყოფით წიბოებსაც უმკლავდება, თუ უარყოფითი ციკლი არ არის (თორემ „უმოკლესს“ აზრი აღარ აქვს).

მაგალითის გრაფში ორი წიბო უარყოფითია. 1-დან 2-მდე უიაფესი გზა საერთოდ არ არის პირდაპირი წიბო: 1 → 3 → 4 → 2 ღირს −2 + 2 − 1 = −1. ასეთი მარშრუტების პოვნა 16-ვე წყვილისთვის არის ამოცანა.

კოდში V მატრიცა არ გვჭირდება. ერთ მატრიცას ადგილზე ვაახლებთ:

for k: for i: for j: d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ეს უსაფრთხოა, რადგან k-ურ რაუნდში d[i][k] და d[k][j] არ იცვლება (k-მდე მისასვლელად k-ზე გავლა ვერ დაგვეხმარება).

ერთადერთი წესი: k ყველაზე გარე ციკლი უნდა იყოს. ის დპ-ის ფენაა, i და j კი ამ ფენის უჯრებია. k-ს შიგნით ჩასმა ზოგ გრაფზე არასწორ პასუხს იძლევა, ეს კლასიკური შეცდომაა.

ორი ბონუსი. განახლებისას შეინახე next[i][j], რომ გზები აღადგინო. ციკლების შემდეგ კი ნებისმიერი d[i][i] < 0 i-ზე გამავალ უარყოფით ციკლს ავლენს. O(V³) დროითა და O(V²) მეხსიერებით ფლოიდ-ვორშელი სწორი არჩევანია, როცა V დაახლოებით 400–500-მდეა, გრაფი მკვრივია ან მართლა ყველა წყვილი გჭირდება.