უმოკლესი გზების განსაზღვრა ევკლიდურ გრაფებში

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

მიმაგრებული ფაილები: