იცით, რატომ არის ის უფრო სწორ ხაზზე, ვიდრე რკალში? ორ პარალელურ წრფეს შორის მანძილის დადგენა რა არის უმოკლესი მანძილი ორ წერტილს შორის

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

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

ნავიგაციაში ამ რთულ ორმაგ მრუდის ხაზს ე.წ ლოქსოდრომია, რაც ბერძნულად ნიშნავს „დახრილ რბენას“.

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

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

ნავიგაციაში დიდი წრის რკალი ეწოდება დიდი წრე, რაც ნიშნავს "სწორ გარბენს". დიდი წრის მეორე თავისებურება ის არის, რომ იგი კვეთს მერიდიანებს სხვადასხვა კუთხით (სურ. 29).

დედამიწის ზედაპირის ორ წერტილს შორის მანძილის განსხვავება ლოქსოდრომისა და ორთოდრომის გასწვრივ პრაქტიკული მნიშვნელობისაა მხოლოდ დიდი ოკეანის გადასასვლელებისთვის.

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

განტოლების გამოსატანად ვიღებთ ლოქსოდრომებს (ნახ. 30, ა) ორი წერტილი მაგრამდა AT,მათ შორის მანძილი უბრალოდ მცირეა. მერიდიანებისა და მათ შორის პარალელის გავლებით, ვიღებთ ელემენტარულ მართკუთხა სფერულ სამკუთხედს ABC.ამ სამკუთხედში მერიდიანისა და პარალელის გადაკვეთით წარმოქმნილი კუთხე სწორია, ხოლო კუთხე პნABტოლია გემის K. Katet ACწარმოადგენს მერიდიანის რკალის სეგმენტს და შეიძლება იყოს გამოხატული

სადაც რ - სფეროს სახით აღებული დედამიწის რადიუსი;

Δφ - გრძედის ელემენტარული ზრდა (გრძედების განსხვავება).

ფეხი სვწარმოადგენს რკალის პარალელურ სეგმენტს

სადაც რ - პარალელის რადიუსი;

Δλ - გრძედის ელემენტარული განსხვავება.

სამკუთხედიდან OO 1 C შეიძლება მოიძებნოს რომ

შემდეგ საბოლოო ფორმაში ფეხი სვშეიძლება გამოიხატოს ასე:

ვივარაუდოთ ელემენტარული სფერული სამკუთხედი ABCბინისთვის დაწერე

შემცირების შემდეგ რ და კოორდინატების ელემენტარული მცირე ნამატების ჩანაცვლება უსასრულო მცირეებით, გვაქვს

ჩვენ ვაერთიანებთ შედეგად გამოსახულებას φ 1, λ 1-დან φ 2-მდე დიაპაზონში, λ 2 tgK-ის მნიშვნელობის მუდმივი მნიშვნელობის გათვალისწინებით:

მარჯვენა მხარეს გვაქვს ცხრილის ინტეგრალი. მისი მნიშვნელობის ჩანაცვლების შემდეგ ვიღებთ ლოქსოდრომის განტოლებას ბურთზე

ამ განტოლების ანალიზი საშუალებას გვაძლევს გამოვიტანოთ შემდეგი დასკვნები:

0 და 180 ° კურსებზე ლოქსოდრომი იქცევა დიდი წრის რკალად - მერიდიანად;

90 და 270 ° კურსებზე ლოქსდრომი ემთხვევა პარალელურს;

ლოქსოდრომი თითოეულ პარალელს მხოლოდ ერთხელ კვეთს და ყოველ მერიდიანს უთვალავი რამდენჯერ. იმათ. სპირალურად უახლოვდება ბოძს, არ აღწევს მას.

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

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

1. ლოქსოდრომი, რომელიც კვეთს მერიდიანებს მუდმივი კუთხით, გამოსახული უნდა იყოს სწორი ხაზით.

2. რუკის პროექცია, რომელიც გამოიყენება რუქების ასაგებად, უნდა იყოს ტოლკუთხა ისე, რომ მასზე არსებული კურსები, საკისრები და კუთხეები შეესაბამებოდეს მათ მნიშვნელობას ადგილზე.

3. მერიდიანები და პარალელები, ისევე როგორც კურსის ხაზები 0, 90, 180° და 270°, უნდა იყოს ორმხრივი პერპენდიკულარული სწორი ხაზები.

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

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

და ვისაც სურს კიდევ უფრო მეტი მიიღოს საინტერესო ინფორმაციაგაიგე მეტი ორიგინალი სტატია განთავსებულია საიტზე InfoGlaz.rfსტატიის ბმული, საიდანაც შედგენილია ეს ასლი -

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

მანძილი- არსებითი სახელი, ს., გამოყენება. ხშირად მორფოლოგია: (არა) რა? მანძილი რისთვის? მანძილი, (იხილეთ) რა? მანძილი ვიდრე? მანძილი, რა? მანძილის შესახებ; pl. რა? მანძილი, (არა) რა? დისტანციები, რატომ? დისტანციები, (იხილეთ) რა? მანძილი ვიდრე? დისტანციებზე... დიმიტრიევის ლექსიკონი

მანძილი- ᲛᲔ; შდრ. სივრცე, რომელიც ჰყოფს ორ წერტილს, ორ საგანს და ა.შ., უფსკრული ვინმეს შორის, ვიდრე l. ყველაზე მოკლე მდინარე ორ წერტილს შორის. სახლიდან სკოლამდე რ. უკან დახევა ახლომდებარე მდინარეში. მეტრის მანძილზე, ხელები გაშლილი. იცოდე რაღაც, იგრძენი რაღაც. ზე… … ენციკლოპედიური ლექსიკონი

მანძილი- ᲛᲔ; შდრ. იხილეთ ასევე მანძილი ა) სივრცე, რომელიც აშორებს ორ წერტილს, ორ საგანს და ა.შ., უფსკრული ვინმეს შორის, ვიდრე l. უმოკლესი მანძილი ორ წერტილს შორის. მანძილი სახლიდან სკოლამდე. უკან დახევა ახლო მანძილზე / არა ... მრავალი გამოთქმის ლექსიკონი

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

ნავიგაცია*

ნავიგაცია- ნავიგაციის დეპარტამენტი (იხ.), ზღვაზე გემის ადგილის განსაზღვრის გზების პრეზენტაციის დასრულება კომპასისა და ჟურნალის გამოყენებით (იხ.). ზღვაზე გემის ადგილის დადგენა ნიშნავს რუკაზე განთავსდეს წერტილი, რომელშიც გემი იმყოფება ამ მომენტშიმდებარეობს…… ენციკლოპედიური ლექსიკონი F.A. ბროკჰაუსი და ი.ა. ეფრონი

კოგენი- (კოენ) ჰერმანი (1842 1918) გერმანელი ფილოსოფოსი, მარბურგის ნეოკანტიანიზმის სკოლის დამაარსებელი და ყველაზე თვალსაჩინო წარმომადგენელი. ძირითადი ნაშრომები: "კანტის გამოცდილების თეორია" (1885), "კანტის ეთიკის დასაბუთება" (1877), "კანტის ესთეტიკის დასაბუთება" (1889), "ლოგიკა... ...

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

კანტის კრიტიკული ფილოსოფია: დოქტრინა შესაძლებლობების შესახებ- (La philosophie critique de Kant: Doctrines des facultes, 1963) დელოზი. შესავალში ტრანსცენდენტული მეთოდის აღწერისას დელუზი აღნიშნავს, რომ კანტი ფილოსოფიას ესმის, როგორც მეცნიერებას მთელი ცოდნის მიმართ არსებით მიზნებთან... ... ფილოსოფიის ისტორია: ენციკლოპედია

ფერმის პრინციპი- გეომეტრიული ოპტიკის ძირითადი პრინციპი (იხ. გეომეტრიული ოპტიკა). F. p.-ის უმარტივესი ფორმა არის განცხადება, რომ სინათლის სხივი ყოველთვის ვრცელდება სივრცეში ორ წერტილს შორის ბილიკის გასწვრივ, რომლის გასწვრივ მისი გავლის დრო ნაკლებია, ვიდრე ... Დიდი საბჭოთა ენციკლოპედია

(აღწერითი გეომეტრია)

CD (CXDX, C2D2)ნაჩვენებია როგორც წერტილი C5 = D5 A5B5უდრის...
(აღწერითი გეომეტრია)

ორ პარალელურ სიბრტყეს შორის მანძილის განსაზღვრა

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

ორ გადამკვეთ წრფეს შორის მანძილის განსაზღვრა

თუ გსურთ განსაზღვროთ უმოკლესი მანძილი ორ გადამკვეთ ხაზს შორის, თქვენ უნდა შეცვალოთ საპროექციო სიბრტყეების სისტემები ორჯერ. ამ პრობლემის გადაჭრისას პირდაპირი CD (CXDX, C2D2)ნაჩვენებია როგორც წერტილი C5 = D5(სურ. 198). მანძილი ამ წერტილიდან პროექციამდე A5B5უდრის...
(აღწერითი გეომეტრია)

კუთხე ორ გადამკვეთ სწორ ხაზს შორის

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

ორ პარალელურ წრფეს შორის მანძილის განსაზღვრა

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

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

მოსწავლე დაფიქრების შემდეგ გულმოდგინედ ხაზავს მათ შორის მიხვეულ ხაზს.

- ეს ყველაზე მოკლე გზაა! მასწავლებელი გაკვირვებულია. -ეს ვინ გასწავლა?

- Მამაჩემი. ის ტაქსის მძღოლია.

გულუბრყვილო სკოლის მოსწავლის ნახატი, რა თქმა უნდა, ანეკდოტურია, მაგრამ არ გაიღიმებდით, თუ გეტყვით, რომ ლეღვის წერტილოვანი რკალი. 1 არის უმოკლესი გზა კარგი იმედის კონცხიდან ავსტრალიის სამხრეთ მწვერვალამდე!

კიდევ უფრო გასაოცარია შემდეგი განცხადება: გამოსახულია ნახ. 2 ორმხრივი მოგზაურობა იაპონიიდან პანამის არხამდე უფრო მოკლეა, ვიდრე იმავე რუკაზე მათ შორის დახატული სწორი ხაზი!

ბრინჯი. 1. ჩართული ზღვის რუკაუმოკლესი გზა კარგი იმედის კონცხიდან ავსტრალიის სამხრეთ წვერამდე არ არის მითითებული სწორი ხაზით ("ლოქსდრომი"), არამედ მრუდით ("ორთოდრომია")

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

ბრინჯი. 2. წარმოუდგენელია, რომ იოკოჰამას ზღვის რუკაზე პანამის არხთან დამაკავშირებელი მოსახვევი ბილიკი უფრო მოკლეა, ვიდრე იმავე წერტილებს შორის დახატული სწორი ხაზი.

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

მეზღვაურები იყენებენ XVI საუკუნის ძველი ჰოლანდიელი კარტოგრაფისა და მათემატიკოსის მეთოდით შედგენილ რუკებს. მერკატორი. ამ მეთოდს მერკატორის პროექცია ეწოდება. ადვილია ზღვის რუქის ამოცნობა მართკუთხა ბადით: მასზე მერიდიანები ნაჩვენებია პარალელური სწორი ხაზების წყების სახით; გრძედი წრეები - ასევე პირველის პერპენდიკულარულ სწორ ხაზებში (იხ. სურ. 5).

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

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

ბრინჯი. 3. მარტივი გზა ორ წერტილს შორის მართლაც უმოკლეს გზის მოსაძებნად: ამ წერტილებს შორის გლობუსზე ძაფის გაჭიმვა გჭირდებათ.

ნათქვამის შემდეგ ირკვევა, თუ რატომ არის გამოსახული უმოკლესი გზა ზღვის რუკაზე არა როგორც სწორი, არამედ მრუდი ხაზი.

ისინი ამბობენ, რომ ნიკოლაევსკაიას მიმართულების არჩევისას (ახლა ოქტიაბრსკაია) რკინიგზაიყო გაუთავებელი კამათი იმის შესახებ, თუ რა გზით უნდა ჩაეყარა იგი. კამათს წერტილი დაუსვა ცარ ნიკოლოზ I-ის ჩარევამ, რომელმაც პრობლემა ფაქტიურად „სწორად“ გადაჭრა: მან ხაზის გასწვრივ პეტერბურგი მოსკოვს დაუკავშირა. ეს რომ გაკეთებულიყო მერკატორის რუკაზე, ეს იქნებოდა უხერხული სიურპრიზი: სწორი ხაზის ნაცვლად, გზა მოსახვევი აღმოჩნდებოდა.

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

ბრინჯი. 4. ბურთზე A და B წერტილებს შორის მანძილების გამოსათვლელად პარალელის რკალის გასწვრივ და დიდი წრის რკალის გასწვრივ

ნახ. 4 ქულა ო -ცენტრი გლობუსი, AB -გრძედის წრის რკალი, რომელზედაც მდებარეობს ნავსადგურები A და B; inმისი 60°. გრძედი წრის ცენტრი არის წერტილში FROMწარმოიდგინეთ ეს ცენტრიდან ოდედამიწის იმავე ნავსადგურებში არის გამოყვანილი დიდი წრის რკალი: მისი რადიუსი OB = OA = R;იგი გაივლის შედგენილ რკალთან ახლოს AB,მაგრამ არ ემთხვევა.

გამოვთვალოთ თითოეული რკალის სიგრძე. მას შემდეგ, რაც რაოდენობა მაგრამდა ATდაწექი 60° განედზე, შემდეგ რადიუსი OAდა OVშეადგინოს OS(გლობუსის ღერძი) კუთხე 30°. მართკუთხა სამკუთხედში ASOფეხი AC (=r), 30° კუთხის საპირისპიროდ დაწოლა უდრის ჰიპოტენუზის ნახევარს სს;

ნიშნავს, r=R/2რკალის სიგრძე ABარის გრძედის წრის სიგრძის მეექვსედი და რადგან ამ წრეს აქვს დიდი წრის სიგრძის ნახევარი (რადიუსის ნახევარი), მაშინ მცირე წრის რკალის სიგრძე

იმისთვის, რომ განვსაზღვროთ ერთსა და იმავე წერტილებს შორის შედგენილი დიდი წრის რკალის სიგრძე (ანუ უმოკლესი გზა მათ შორის), ჩვენ უნდა ვიცოდეთ კუთხის სიდიდე. AOW.აკორდი ასრკალი 60 °-მდე გამოკლება (პატარა წრე), არის იმავე მცირე წრეში ჩაწერილი რეგულარული ექვსკუთხედის მხარე; ამიტომაც AB \u003d r \u003d R / 2

სწორი ხაზის დახატვა od,დამაკავშირებელი ცენტრი ოგლობუსი შუათან დაკორდები AB,მიიღეთ მართკუთხა სამკუთხედი ODA,სად არის კუთხე D-სწორი:

DA= 1/2 AB და OA=R.

sinAOD=AD: AO=R/4:R=0.25

აქედან ვპოულობთ (ცხრილების მიხედვით):

=14°28",5

და აქედან გამომდინარე

= 28°57"

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

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

ძაფით შეიარაღებული და ხელთ გაქვთ გლობუსი, შეგიძლიათ მარტივად შეამოწმოთ ჩვენი ნახატების სისწორე და დარწმუნდეთ, რომ დიდი წრეების რკალი ნამდვილად დევს, როგორც ეს ნახატებშია ნაჩვენები. ნაჩვენებია ნახ. 1 თითქოს "სწორი" საზღვაო გზა აფრიკიდან ავსტრალიამდე არის 6020 მილი, ხოლო "მრუდი" - 5450 მილი, ანუ უფრო მოკლეა 570 მილით, ანუ 1050 კმ-ით. „პირდაპირი“ საჰაერო მარშრუტი ზღვის სქემაზე ლონდონიდან შანხაიში კვეთს კასპიის ზღვას, ხოლო მართლაც უმოკლესი მარშრუტი მდებარეობს სანკტ-პეტერბურგის ჩრდილოეთით. გასაგებია, რა როლს თამაშობს ეს საკითხები დროისა და საწვავის დაზოგვაში.

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

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

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

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

მეზღვაურების მიდრეკილება მერკატორის რუკებზე ახლა გასაგებია. დანიშნულ პორტში გასვლისას გასავლელი კურსის განსაზღვრის სურვილით, ნავიგატორი მიმართავს სახაზავს ბილიკის ბოლო წერტილებს და ზომავს მის კუთხეს მერიდიანებთან. ამ მიმართულებით მუდმივად ღია ზღვაში ყოფნისას, ნავიგატორი ზუსტად მიიყვანს გემს სამიზნემდე. ხედავთ, რომ "ლოქსოდრომი" მართალია არა უმოკლესი და არც ყველაზე ეკონომიური, მაგრამ გარკვეულწილად ძალიან მოსახერხებელი გზაა მეზღვაურისთვის. მაგალითად, კარგი იმედის კონცხიდან ავსტრალიის სამხრეთ მწვერვალამდე მისასვლელად (იხ. სურ. 1), ყოველთვის უნდა შეინარჩუნოთ იგივე კურსი S 87 °.50 ". იმავდროულად, იმისთვის, რომ გემი იმავე ადგილზე მიიყვანოთ. საბოლოო წერტილი უმოკლესი გზა(„ორთოდრომიის“ მიხედვით), აუცილებელია, როგორც ნახატიდან ჩანს, ჭურჭლის კურსის მუდმივად შეცვლა: იწყება კურსიდან S 42 °, 50“ და დასრულდება კურსით N 53 °, 50. (ამ შემთხვევაში, უმოკლესი გზა არც კი არის შესაძლებელი - ის ანტარქტიდის ყინულის კედელშია ჩასმული).

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

Dijkstra-ს ალგორითმი არის გრაფიკული ალგორითმი, რომელიც გამოიგონა ჰოლანდიელმა მეცნიერმა Edsger Dijkstra-მ 1959 წელს. პოულობს უმოკლეს ბილიკებს გრაფიკის ერთ-ერთი წვეროდან ყველა დანარჩენამდე. მუშაობს ალგორითმი მხოლოდ გრაფიკებისთვის უარყოფითი წონის კიდეების გარეშე.

განვიხილოთ ალგორითმის შესრულება ნახატზე ნაჩვენები გრაფიკის მაგალითზე.

დაე, მოითხოვოს უმოკლესი მანძილების პოვნა 1-ლი წვეროდან ყველა დანარჩენამდე.

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

Პირველი ნაბიჯი. ჩვენი მაგალითისთვის განვიხილოთ დიკსტრას ალგორითმის ნაბიჯი. Vertex 1-ს აქვს მინიმალური ეტიკეტი. წვეროები 2, 3 და 6 არის მისი მეზობლები.

1-ის პირველი მეზობელი თავის მხრივ არის წვერო 2, რადგან მისკენ მიმავალი ბილიკის სიგრძე მინიმალურია. მისკენ მიმავალი ბილიკის სიგრძე 1 წვეროში უდრის 1-ლი წვეროს ეტიკეტის მნიშვნელობის ჯამს და 1-დან მე-2-მდე მიმავალი კიდის სიგრძის, ანუ 0 + 7 = 7. ეს ნაკლებია ვიდრე 2 წვერის მიმდინარე ეტიკეტი, უსასრულობა, ასე რომ, მე-2 წვერის ახალი ეტიკეტი არის 7.

ანალოგიურ ოპერაციას ვასრულებთ 1-ლი წვერის კიდევ ორ მეზობელთან - მე-3 და მე-6-თან.

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

მეორე ნაბიჯი. ალგორითმის ნაბიჯი მეორდება. კვლავ ვპოულობთ დაუთვალიერებელ წვეროებს „უახლოეს“. ეს არის 2 წვერო, რომელსაც აქვს 7.

კვლავ ვცდილობთ შევამციროთ არჩეული წვერის მეზობლების ეტიკეტები, ვცდილობთ მათში გავიაროთ მე-2 წვეროზე. Vertex 2-ის მეზობლები არიან წვეროები 1, 3 და 4.

მე-2 წვეროს პირველი (მიმდევრობით) მეზობელი არის წვერო 1. მაგრამ ის უკვე მონახულებულია, ამიტომ 1-ლ წვეროსთან არაფერს ვაკეთებთ.

მე-2 წვერის შემდეგი მეზობელი არის წვერო 3, რადგან მას აქვს წვეროების მინიმალური ეტიკეტი, რომელიც მონიშნულია როგორც დაუთვალიერებელი. თუ მასზე 2-ით მიდიხართ, მაშინ ასეთი ბილიკის სიგრძე იქნება 17 (7 + 10 = 17). მაგრამ მესამე წვერის მიმდინარე ეტიკეტი არის 9, რაც 17-ზე ნაკლებია, ამიტომ ეტიკეტი არ იცვლება.

მე-2 წვეროს კიდევ ერთი მეზობელი არის წვერო 4. თუ მას მე-2-ით მიდიხართ, მაშინ ასეთი ბილიკის სიგრძე ტოლი იქნება მე-2 წვერომდე უმოკლესი მანძილის ჯამისა და 2 და 4 წვეროებს შორის მანძილის ჯამის, ე.ი. , 22 (7 + 15 = 22) . 22 წლიდან<, устанавливаем метку вершины 4 равной 22.

მე-2 წვერის ყველა მეზობელი ნანახია, ჩვენ ვყინავთ მასამდე მანძილს და ვნიშნავთ, როგორც მონახულებულს.

მესამე ნაბიჯი. ვიმეორებთ ალგორითმის საფეხურს მე-3 წვერის არჩევით. მისი „დამუშავების“ შემდეგ ვიღებთ შემდეგ შედეგებს:

Შემდეგი ნაბიჯები. ჩვენ ვიმეორებთ ალგორითმის საფეხურს დარჩენილი წვეროებისთვის. ეს იქნება 6, 4 და 5 წვეროები, შესაბამისად.

ალგორითმის შესრულების დასრულება. ალგორითმი მთავრდება მაშინ, როცა მეტი წვეროების დამუშავება შეუძლებელია. ამ მაგალითში ყველა წვერო გადაკვეთილია, მაგრამ შეცდომაა ვივარაუდოთ, რომ ეს ასე იქნება ნებისმიერ მაგალითში - ზოგიერთი წვერო შეიძლება დარჩეს გადაკვეთილი, თუ მათი მიღწევა შეუძლებელია, ანუ თუ გრაფიკი გათიშულია. ალგორითმის შედეგი ჩანს ბოლო ფიგურაში: უმოკლესი გზა 1-დან 2-მდე არის 7, 3-მდე არის 9, 4-მდე არის 20, 5-მდე არის 20, 6-მდე არის 11.

ალგორითმის დანერგვა პროგრამირების სხვადასხვა ენაზე:

C++

#include "stdafx.h" #include namespace std-ის გამოყენებით; const int V=6; // Dijkstra-ს ალგორითმი void Dijkstra(int GR[V][V], int st) ( int მანძილი[V], რაოდენობა, ინდექსი, i, u, m=st+1; bool visited[V]; for (i= 0 ი "< "<> "; cin>>დაწყება; Dijkstra (GR, დაწყება-1); სისტემა ("პაუზა>>ბათილი"); )

პასკალი

პროგრამა DijkstraAlgorithm; usecrt; constV=6; inf=100000; type vector=მთლიანი რიცხვის მასივი; var start: მთელი რიცხვი; const GR: მთელი რიცხვების მასივი=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); (Dijkstra-ს ალგორითმი) პროცედურა Dijkstra(GR: მთელი რიცხვების მასივი; st: მთელი რიცხვი); var რაოდენობა, ინდექსი, i, u, m, min: მთელი რიცხვი; მანძილი: ვექტორი; ეწვია: ლოგიკური მასივი; დასაწყისი:=st; i:=1-დან V-მდე დაიწყეთ მანძილი[i]:=inf; ეწვია[i]:=false; დასასრული; მანძილი:=0; დათვლისთვის:=1-დან V-1-მდე დაიწყეთ min:=inf; i:=1-დან V-მდე გააკეთეთ თუ (არ მოინახულეთ[i]) და (დისტანცია[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) და (მანძილი[u]<>inf) და (მანძილი[u]+GR inf შემდეგ writeln(m," > ", i," = ", მანძილი[i]) else writeln(m," > ", i," = ", "მარშრუტი მიუწვდომელია"); დასასრული; (მთავარი პროგრამის ბლოკი) start clrscr; write ("საწყისი კვანძი >> "); წაკითხვა (დაწყება); Dijkstra (GR, დაწყება); დასასრული.

ჯავა

იმპორტი java.io.BufferedReader; იმპორტი java.io.IOException; იმპორტი java.io.InputStreamReader; იმპორტი java.io.PrintWriter; იმპორტი java.util.ArrayList; იმპორტი java.util.Arrays; იმპორტი java.util.StringTokenizer; საჯარო კლასი Solution ( private static int INF = Integer.MAX_VALUE / 2; private int n; // წვეროების რაოდენობა დიგრაფში private int m; //რკალების რაოდენობა დიგრაფში private ArrayList ადგ; //მიმდებარეობის სია კერძო ArrayList წონა; //კიდის წონა დიგრაფიულ კერძო ლოგინში გამოყენებული; //მაივი ინფორმაციის შესანახად გავლილი და არგავლილი მწვერვალების შესახებ private int dist; //მასივი საწყისი წვეროდან მანძილის შესანახად //წინაპრების მასივი, რომელიც საჭიროა საწყისი წვეროდან უმოკლესი გზის აღსადგენად private int pred; int დაწყება; //საწყისი წვერო, საიდანაც ყველა დანარჩენამდე მანძილი იძებნება private BufferedReader cin; კერძო PrintWriter cout; კერძო StringTokenizer ტოკენიზატორი; //დიკსტრას ალგორითმის დაწყების პროცედურა საწყისი წვეროდან private void dejkstra(int s) ( dist[s] = 0; //საწყის წვერომდე უმოკლესი მანძილი არის 0 for (int iter = 0; iter< n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { cin = new BufferedReader(new InputStreamReader(System.in)); cout = new PrintWriter(System.out); tokenizer = new StringTokenizer(cin.readLine()); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayList(); ) //სიის ინიციალიზაცია, რომელიც ინახავს კიდეების წონებს weight = new ArrayList[n]; for (int i = 0; i< n; ++i) { weight[i] = new ArrayList(); ) //წაიკითხეთ კიდეების სიით მოცემული გრაფიკი (int i = 0; i< m; ++i) { tokenizer = new StringTokenizer(cin.readLine()); int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } }

კიდევ ერთი ვარიანტი:

java.io.* იმპორტი; იმპორტი java.util.*; საჯარო კლასი Dijkstra ( კერძო სტატიკური საბოლოო Graph.Edge GRAPH = ( new Graph.Edge("a", "b", 7), new Graph.Edge("a", "c", 9), new Graph.Edge( "a", "f", 14), new Graph.Edge("b", "c", 10), new Graph.Edge("b", "d", 15), new Graph.Edge("c ", "d", 11), new Graph.Edge("c", "f", 2), new Graph.Edge("d", "e", 6), new Graph.Edge("e", "f", 9), ); კერძო სტატიკური საბოლოო სტრიქონი START = "a"; კერძო სტატიკური საბოლოო სტრიქონი END = "e"; საჯარო სტატიკური სიცარიელე მთავარი (სტრიქონის არგები) (გრაფიკი g = ახალი გრაფიკი (GRAPH); g.dijkstra (START); g.printPath(END); //g.printAllPaths(); ) ) კლასის გრაფიკი ( პირადი საბოლოო რუკა გრაფიკი; // წვეროების სახელების გამოსახვა ვერტექსის ობიექტებზე, აგებულია კიდეების სიმრავლიდან /** გრაფის ერთი კიდე (მხოლოდ Graph-ის კონსტრუქტორი გამოიყენება) */ საჯარო სტატიკური კლასი Edge ( საჯარო საბოლოო სტრიქონი v1, v2; საჯარო საბოლოო int dist; საჯარო კიდე(სტრიქონი v1, სტრიქონი v2, int dist) ( this.v1 = v1; this.v2 = v2; this.dist = dist; ) ) /** გრაფის ერთი წვერო, დასრულებული მეზობელ წვეროებთან შეხამებით */ საჯარო სტატიკური კლასი Vertex ახორციელებს Comparable ( საჯარო საბოლოო სტრიქონის სახელი; საჯარო int dist = Integer.MAX_VALUE; // MAX_VALUE ჩათვლილია უსასრულობის საჯარო წვეროზე წინა = null; საჯარო საბოლოო რუკა მეზობლები = ახალი HashMap<>(); public Vertex(string name) ( this.name = name; ) private void printPath() ( if (this == this.previous) ( System.out.printf ("%s", this.name); ) else if ( this.previous == null) ( System.out.printf("%s(მიუწვდომელი)", this.name); ) else (this.previous.printPath(); System.out.printf(" -> %s( %d)", this.name, this.dist); ) ) public int compareTo(Vertex other) ( return Integer.compare(dist, other.dist); ) ) /** აშენებს გრაფიკს კიდეების სიმრავლიდან * / public Graph(Edge edges) (გრაფი = ახალი HashMap<>(კიდეები.სიგრძე); //ერთი გადასასვლელი ყველა წვერის საპოვნელად (Edge e: edges) (if (!graph.containsKey(e.v1)) graph.put(e.v1, new vertex(e.v1)); if (!graph. შეიცავსKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); ) //სხვა უღელტეხილი მეზობელი წვეროების დასაყენებლად (Edge e: edges) ( graph.get(e.v1). Neighbours.put(graph.get(e.v2), e.dist); //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // ასევე გააკეთეთ ეს არამიმართული გრაფიკისთვის ) ) /** აწარმოებს dijkstra-ს მითითებული წყაროს წვერის გამოყენებით */ public void dijkstra(String startName) ( if (!graph.containsKey(startName)) ( System.err.printf("გრაფიკი არ შეიცავს საწყისი წვეროს \"%s\"\n", startName); დაბრუნება; ) საბოლოო წვერო = graph.get(startName); NavigableSet q = ახალი ხეების ნაკრები<>(); // წვეროების დაყენება (Vertex v: graph.values()) ( v.previous = v == წყარო ? წყარო: null; v.dist = v == წყარო ? 0: Integer.MAX_VALUE; q.add( v);) dijkstra(q); ) /** dijkstra-ს ალგორითმის დანერგვა ბინარული გროვის გამოყენებით. */ private void dijkstra(final NavigableSet q) ( წვერო u, v; while (!q.isEmpty()) (u = q.pollFirst(); // წვერო უმოკლესი მანძილით (პირველი გამეორება დააბრუნებს წყაროს) თუ (u.dist == Integer.MAX_VALUE) შესვენება; // ჩვენ შეგვიძლია უგულებელვყოთ u (და ნებისმიერი სხვა დარჩენილი წვერო), რადგან ისინი მიუწვდომელია //შეხედეთ დისტანციებს თითოეულ მეზობლამდე (Map.Entry a: u.neighbours.entrySet()) (v = a.getKey(); //მეზობელი ამ გამეორებაში საბოლოო int alternateDist = u.dist + a.getValue(); if (alternateDist< v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } }

C

#შეიცავს #შეიცავს #შეიცავს //#define BIG_EXAMPLE typedef struct node_t node_t, *heap_t; typedef struct edge_t edge_t; struct edge_t ( node_t *nd; /* სამიზნე ამ კიდეზე */ edge_t *ძმა;/* ცალკე დაკავშირებული სიისთვის */ int len; /* კიდეების ღირებულება */ ); struct node_t ( edge_t *edge; /* კიდეების ცალმხრივად დაკავშირებული სია */ node_t *via; /* სადაც წინა კვანძი არის უმოკლეს გზაზე */ ორმაგი დაშორება; /* მანძილი საწყისი კვანძიდან */ char სახელი; /* the, er , სახელი */ int heap_idx; /* ბმული გროვის პოზიციაზე მანძილის განახლებისთვის */ ); /* --- კიდეების მართვა --- */ #ifdef BIG_EXAMPLE # განსაზღვრა BLOCK_SIZE (1024 * 32 - 1) #else # განსაზღვრა BLOCK_SIZE 15 #endif edge_t *edge_root = 0, *e_next = 0; /* არ იდარდოთ მეხსიერების მართვის საკითხებზე, ისინი აზრზე არიან. პრეტენზია e_next = malloc(sizeof(edge_t)) */ void add_edge(node_t *a, node_t *b, double d) ( if (e_next == edge_root ) ( edge_root = malloc(sizeof(edge_t) * (BLOCK_SIZE + 1)); edge_root.sibling = e_next; e_next = edge_root + BLOCK_SIZE; ) --e_next; e_next->nd = b; e_next-_>len = d; ->ძმა = a->Edge; a->Edge = e_next; ) void free_edges() ( for (; edge_root; edge_root = e_next) (e_next = edge_root.sibling; თავისუფალი (edge_root); ) ) /* --- პრიორიტეტული რიგის პერსონალი --- */ heap_t *heap; int heap_len; void set_dist(node_t *nd, node_t *via, double d) ( int i, j; /* უკვე იცოდა უკეთესი გზა */ if (nd->via && d >= nd->dist) დაბრუნება; /* იპოვეთ არსებული გროვის ჩანაწერი, ან შექმენით ახალი */ nd->dist = d; nd->via = via; i = nd->Heap_idx; თუ (!i) i = ++ heap_len; /* upheap */ for (; i > 1 && nd->dist< heap->დაშორება; i = j) (heap[i] = heap[j])-> heap_idx = i; heap[i] = nd; nd-> heap_idx = i; ) node_t * pop_queue() ( node_t *nd, *tmp; int i, j; თუ (!heap_len) დააბრუნებს 0; /* ამოიღეთ წამყვანი ელემენტი, გაიყვანეთ კუდის ელემენტი იქ და downheap */ nd = გროვა; tmp = გროვა; for (i = 1; i< heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist > heap->dist) j++; if (heap[j]->dist >= tmp->dist) break; (heap[i] = heap[j])->heap_idx = i; ) heap[i] = tmp; tmp->heap_idx = i; დაბრუნება nd; ) /* --- Dijkstra პერსონალი; მიუწვდომელი კვანძები არასოდეს შეიქმნება შევიდარიგი --- */ void calc_all(node_t *start) ( node_t *lead; edge_t *e; set_dist(start, start, 0); while ((lead = pop_queue())) for (e = lead->edge; e; e = e-> ძმა) set_dist(e->nd, lead, lead->dist + e->len); ) void show_path(node_t *nd) (if (nd->via == nd) printf( "%s", nd->name); სხვა შემთხვევაში, თუ (!nd->via) printf("%s(მიუწვდომელი)", nd->name); else ( show_path(nd->via); printf("- > %s(%g) ", nd->name, nd->dist); ) ) int main(void) ( #ifndef BIG_EXAMPLE int i; # define N_NODES ("f" - "a" + 1) node_t * კვანძები = calloc(sizeof(node_t), N_NODES); for (i = 0; i< N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; }

PHP

$edge, "cost" => $edge); $neighbours[$edge] = მასივი ("end" => $edge, "cost" => $edge); ) $ vertices = array_unique ($ vertices); foreach ($vertices როგორც $vertex) ( $dist[$vertex] = INF; $წინა[$vertex] = NULL; ) $dist[$source] = 0; $Q = $ვერტიკები; while (count($Q) > 0) ( // TODO - იპოვნეთ უფრო სწრაფი გზა მინიმუმ $min = INF-ის მისაღებად; foreach ($Q როგორც $vertex)( if ($dist[$vertex]< $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";

პითონი

კოლექციებიდან იმპორტი namedtuple, რიგი pprint-დან იმპორტი pprint როგორც pp inf = float("inf") Edge = namedtuple("Edge", "start, end, cost") class Graph(): def __init__(self, edges): self .edges = edges2 = self.vertices = set(sum(( for e edges2), )) def dijkstra(self, source, dest): ამტკიცებს წყარო self.vertices dist = (წვერო: inf წვეროსთვის self.ვერტიკებში ) წინა = (წვერო: არცერთი წვეროსთვის self.vertices) dist = 0 q = self.vertices.copy() მეზობლები = (წვერო: set() წვეროსთვის self.vertices) დასაწყისისთვის, დასასრულისთვის, თვითღირებულებისთვის. კიდეები: მეზობლები.add((ბოლო, ღირებულება)) #pp(მეზობლები) ხოლო q: u = min(q, გასაღები=ლამბდა წვერო: dist) q.remove(u) if dist[u] == inf ან u = = dest: შესვენება v-სთვის, ღირებულება მეზობლებში[u]: alt = dist[u] + ღირებულება, თუ alt< dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u #pp(previous) s, u = deque(), dest while previous[u]: s.pushleft(u) u = previous[u] s.pushleft(u) return s graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10), ("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6), ("e", "f", 9)]) pp(graph.dijkstra("a", "e")) Output: ["a", "c", "d", "e"]