დეიქსტრას ალგორითმი

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

ეს ალგორითმი ეძებს დადებით წიბოებიან გრაფში უმოკლეს მანძილს ერთი წერტილიდან მეორეში.

ავიღოთ ასეთი გრაფი

გვინდა 0 წვეროდან გადასვლა მეექვსეში.
ალგორითმი ასეთია:

ვწერთ ყველა წვეროს და ქვევით ვაწერთ უმოკლეს მანძილს მაგ წვერომდე 0 დან. თავიდან პირველს ვაწერთ 0ს დანარჩენს ყველას უსასრულობას…
0 1 2 3 4 5 6
0 ∞ ∞ ∞ ∞ ∞ ∞

ვიწყებთ ნოლიდან. ნოლიდან გამოდის 1 2 3 .1ში მისასვლელი გზის სიგრძეა 5. დავაწეროთ 5 და ფრჩხილებში წვეროს რიცხვი რომლიდანაც მივედით(ეს გვჭირდება მაშინ თუ უმოკლესი მანძილის გარდა გვაინტერესბს მარშრუტიც).
0 1 2 3 4 5 6
0 5(0) ∞ ∞ ∞ ∞ ∞
მერე მე-2-ს დავაწეროთ 3 და მესამეს 1. როცა ერთი წვეროდან გამოსასვლელი ყველა წიბო მორჩება უფლება გვაქ მეორე სიის(ანუ ქვედა) უმცირესი დავაფიქსიროთ,რაც ნიშნავს რომ მის წვერომდე მისასვლელი უმოკლეს გზა ნაპოვნია, ამ შემთხვევაში მესამეს ვაფიქსირებთ. შეიძლება გაგიკვირდეთ 4,5,6 არ გვაქ განხილული და რა უფლება გვაქ მაგრამ თუ დაკვირდებით 4,5,6ში რომ მივიდეთ აუცილებელია 1 ან 2 გავიაროთ(პირველი ხომ უკვე გადავარჩიეთ) ხოლო პირველიც და მეორეც მესამეზე მეტია შესაბამისად შეგვიძლია გადავხაზოთ.მაშ:

0 1 2 3 4 5 6
0 5(0) 3(0) 1 ∞ ∞ ∞

შემდეგი ეტაპია გადავარჩიოთ დაფიქსირებული წვეროს გადარჩევა. იგივე გზით. მესამე მიდის მე-4ში და მე-5ში, შესაბამისად მანძილებით 9 და 7… ვაწერთ და გამოგვდის:
0 1 2 3 4 5 6
0 5(0) 3(0) 1 10(3) 8(3) ∞
რადგან აქაც დავამთავრეთ იგივე ლოგიკით გვაქვს უფლება დავაფიქსიროთ უმცირესი მეორე სიიდან(ანუ2 წვერო):
0 1 2 3 4 5 6
0 5(0) 3(0) 1 10(3) 8(3) ∞

თუ დაიქსირებისას უმცირესი ოირია(ან მეტი) არსებითი მნიშვნელობა არ აქვს რომელს დავაფიქრსირებთ პირველს.
შემდეგი ეტაპი: II წვერო, და მისიანები(:D). მეორედან გადის მხოლოდ მეოთხეზე 4 სიგრძით…აქ ვხედავთ რმ ოთხს დაწერილი აქვს უკვე ამიტომ ვწერთ იმას რომელიც უფრო პატარაა ამ შემთხვევაში 3+4<1+9 აქედან გამომდინარე ვაწერთ 7-ს.
ვხაზავთ უმცირესს და გამოდის:
0 1 2 3 4 5 6
0 5 3 1 7 8 ∞

ვატარეტ იგივე ოპერაციოებს მეოთხე წვეროზე და ექვსიანს ეწერება 13 და ფიქსირდება 1ლი:

0 1 2 3 4 5 6
0 5 3 1 7 8 13

ვიხილავთ პირველს რომლის შედეგადაც მეხუთეს გადაეწერება 7 და დაფიქსირდება მე-5-ე:
0 1 2 3 4 5 6
0 5 3 1 7 7 13

შემდეგ ვიხილავთ მეხუთეს 6მდე სჭირდება 15 ამიტომ პასუხზე ზეგავლენას ვერ მოახდენს ამიტომაც პასუხია:13!

ესაც თქვენი დეიქსტრა(ისე გავს დიქსტოსას ხო?: D).