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


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

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

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

გვინდა 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).

Advertisements

5 Responses to “დეიქსტრას ალგორითმი”


  1. 1 :) ნოემბერი 28, 2010, 14:41

    მადლობთ სტატიისთვის…

    კარგი საიტია

  2. 2 თორნიკე კაპანაძე მარტი 28, 2012, 08:19

    კარგი სტატიაა…

  3. 3 GameDevGP სექტემბერი 8, 2012, 11:28

    shemexmiane rogorme saqme maq :D

  4. 4 ირაკლი ქოიავა დეკემბერი 5, 2013, 06:33

    კარგი ალგორითმია, დიდი ამოცანებისთვის საკმაოდ მძიმდება გამოთვლა. 3 წლის წინ დავწერეთ მე და ჩემმა მეგობარმა სივრცეში უმოკლესი მანძილი ერთი წერილიდან ბევს წერტილამდე წინაღობების გათვალისწინებით(წინაღობები მოცემული იყო მეშის სახით) რადგან ყოველ ჯერზე მინიმუმი გვინდა განხილული გზებისა აუცილებელია გროვის გამოყენება. ჩვენ ორობითი მინიმუმის გროვა დავწერეთ. ისე თეორიაში ფიბონაჩის გროვა ჯობნის ცოტათი მარა თეორიაში… :).

  5. 5 luka სექტემბერი 8, 2014, 08:31

    მადლობა, საჭირო სტატიაა, კარგი იქნებოდა დეიქსტრას ლოგარითმულ დროში განხორციელებაც რომ ეწეროს ^_^


კომენტარის დატოვება

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s




სტატისტიკა:

  • 25,496 hits

free counters

აბირჟავებენ


%d bloggers like this: