Գիտե՞ք ինչու է այն ուղիղ գծի վրա ավելի հեռու, քան աղեղի մեջ: Երկու զուգահեռ ուղիղների միջև հեռավորության որոշում Ո՞րն է ամենակարճ հեռավորությունը երկու կետերի միջև

Նկարում պատկերված կետագծի երկայնքով ուղին ավելի կարճ է, քան հոծ գծի ուղին: Եվ հիմա մի փոքր ավելի մանրամասն ծովային երթուղիների օրինակով.

Եթե ​​դուք նավարկեք անընդհատ ընթացքով, ապա նավի շարժման հետագիծը երկայնքով երկրի մակերեսըկլինի կոր, որը կոչվում է մաթեմատիկա լոգարիթմականՊարույր.

Նավագնացության մեջ այս բարդ կրկնակի կորության գիծը կոչվում է լոքսոդրոմիա, որը հունարեն նշանակում է «թեք վազք»։

Այնուամենայնիվ, երկրագնդի երկու կետերի միջև ամենակարճ հեռավորությունը չափվում է մեծ շրջանագծի աղեղի երկայնքով:

Մեծ շրջանագծի աղեղը ստացվում է որպես հետք Երկրի մակերևույթի խաչմերուկից Երկրի կենտրոնով անցնող հարթության հետ՝ վերցված որպես գնդակ։

Նավագնացության մեջ մեծ շրջանի աղեղը կոչվում է մեծ շրջան, ինչը նշանակում է «ուղիղ վազք»։ Մեծ շրջանագծի երկրորդ առանձնահատկությունն այն է, որ այն հատում է միջօրեականները տարբեր անկյուններով (նկ. 29):

Լոքսոդրոմի և օրթոդրոմի երկայնքով Երկրի մակերևույթի երկու կետերի միջև հեռավորությունների տարբերությունը գործնական նշանակություն ունի միայն օվկիանոսի մեծ անցումների համար:

Նորմալ պայմաններում այս տարբերությունն անտեսվում է և նավարկությունն իրականացվում է մշտական ​​ընթացքով, այսինքն. լոքսոդրոմով։

Հավասարումը հանելու համար վերցնում ենք լոքսոդրոմիներ (նկ. 30, ա) երկու կետ ԲԱՅՑև AT,նրանց միջև հեռավորությունը պարզապես փոքր է: Նկարելով միջօրեականներ և դրանց միջով զուգահեռ՝ ստանում ենք տարրական ուղղանկյուն գնդաձև եռանկյուն. ABC.Այս եռանկյունում միջօրեականի և զուգահեռի հատումից առաջացած անկյունը ուղիղ է, իսկ անկյունը. ՊnԱԲհավասար է K. Katet նավի ընթացքին ACներկայացնում է միջօրեական աղեղի հատված և կարող է արտահայտվել

որտեղ Ռ - Երկրի շառավիղը վերցված որպես գունդ;

Δφ - լայնության տարրական աճ (լայնությունների տարբերություն):

ոտքը SWներկայացնում է զուգահեռ աղեղային հատված

որտեղ r - զուգահեռի շառավիղը;

Δλ - երկայնությունների տարրական տարբերություն.

Եռանկյունից OO 1 C կարելի է գտնել, որ

Այնուհետեւ վերջնական ձեւով ոտքը SWկարելի է արտահայտել այսպես.

Ենթադրելով տարրական գնդաձև եռանկյուն ABCբնակարանի համար գրել

Կրճատումից հետո Ռ և կոորդինատների տարրական փոքր աճերը փոխարինելով անվերջ փոքրերով՝ ունենք

Մենք ինտեգրում ենք ստացված արտահայտությունը φ 1, λ 1-ից մինչև φ 2 միջակայքում, λ 2 հաշվի առնելով tgK-ի արժեքը որպես հաստատուն արժեք.

Աջ կողմում մենք ունենք աղյուսակային ինտեգրալ: Դրա արժեքը փոխարինելուց հետո մենք ստանում ենք լոքսոդրոմի հավասարումը գնդակի վրա

Այս հավասարման վերլուծությունը թույլ է տալիս մեզ անել հետևյալ եզրակացությունները.

0 և 180 ° դասընթացներում լոքսոդրոմը վերածվում է մեծ շրջանի կամարի՝ միջօրեականի;

90 և 270 ° դասընթացներում լոքսոդրոմը համընկնում է զուգահեռի հետ.

Լոքսոդրոմը հատում է յուրաքանչյուր զուգահեռ միայն մեկ անգամ, իսկ յուրաքանչյուր միջօրեականը՝ անհաշվելի թվով անգամներ։ դրանք. պարուրաձև մոտենալով բևեռին, այն չի հասնում դրան:

Նավագնացությունը մշտական ​​ընթացքով, այսինքն՝ լոքսոդրոմի երկայնքով, թեև Երկրի վրա երկու կետերի միջև ամենակարճ հեռավորությունը չէ, նա զգալի հարմարավետություն է ներկայացնում նավիգատորի համար:

Ծովային նավագնացության գծապատկերին ներկայացվող պահանջները կարող են ձևակերպվել՝ ելնելով լոքսոդրոմի երկայնքով նավարկության առավելությունից և դրա հավասարման վերլուծության արդյունքներից՝ հետևյալ կերպ.

1. Լոքսոդրոմը, որը հատում է միջօրեականները հաստատուն անկյան տակ, պետք է պատկերվի ուղիղ գծի տեսքով:

2. քարտեզի նախագծում, որն օգտագործվում է քարտեզների կառուցման համար, պետք է լինի հավասարանկյուն, որպեսզի դրա վրա գտնվող անցքերը, առանցքակալները և անկյունները համապատասխանեն իրենց արժեքին գետնի վրա:

3. Մերիդյանները և զուգահեռները, ինչպես 0, 90, 180° և 270° գծերը, պետք է լինեն փոխադարձ ուղղահայաց ուղիղներ:

Երկրի մակերևույթի երկու տրված կետերի միջև ամենակարճ հեռավորությունը, որպես գնդիկ, փոքրն է այս կետերով անցնող մեծ շրջանի կամարներից: Բացառությամբ միջօրեականին կամ հասարակածին հետևող նավի դեպքից, մեծ շրջանագիծը հատում է միջօրեականները տարբեր անկյուններով։ Ուստի նման կորով ընթացող նավը պետք է անընդհատ փոխի իր ընթացքը։ Գործնականում ավելի հարմար է հետևել մի ընթացքի, որը հաստատուն անկյուն է կազմում միջօրեականների հետ և քարտեզի վրա պատկերված է Մերկատորի պրոյեկցիայում ուղիղ գծով՝ լոքսոդրոմով։ Այնուամենայնիվ, մեծ հեռավորությունների վրա օրթոդրոմի և լոքսոդրոմի երկարության տարբերությունը հասնում է զգալի արժեքի: Ուստի նման դեպքերում հաշվարկվում է օրթոդոմը և դրա վրա նշվում են միջանկյալ կետեր, որոնց միջև լողում են լոքսոդրոմով։

Քարտեզագրական պրոյեկցիան, որը համապատասխանում է վերը նշված պահանջներին, առաջարկվել է հոլանդացի քարտեզագիր Ջերարդ Կրամերի (Մերկատոր) կողմից 1569 թվականին: Ի պատիվ դրա ստեղծողի, պրոյեկցիան անվանվել է. Մերկատոր.

Իսկ ով է ուզում ստանալ ավելին հետաքրքիր տեղեկություններիմանալ ավելին Հոդվածի բնօրինակը գտնվում է կայքում InfoGlaz.rfՀղում դեպի այն հոդվածը, որտեղից պատրաստված է այս պատճենը -

ՀԵՌԱՎՈՐՈՒԹՅՈՒՆ, հեռավորություններ, տես. 1. Երկու կետ բաժանող տարածություն, ինչ-որ բանի միջև բացը: Ուղղակի երկու կետերի միջև ամենակարճ հեռավորությունը: Ապրում է մեզանից երկու կիլոմետր հեռավորության վրա: «Հրամանատարը նրանց ներս թողեց ամենամոտ հեռավորության վրա ... ԲառարանՈւշակովը

հեռավորությունը- գոյական, ս., գործածություն։ հաճախ Մորֆոլոգիա. (ոչ) ինչ: հեռավորությունը ինչի՞ համար հեռավորություն, (տես) ինչ: հեռավորությունը քան? հեռավորությունը, ինչ? հեռավորության մասին; pl. ինչ? հեռավորություն, (ոչ) ինչ: հեռավորություններ, ինչու՞ հեռավորություններ, (տես) ինչ: հեռավորությունը քան? հեռավորություններ... Դմիտրիևի բառարան

հեռավորությունը- Ես; տես. Երկու կետ, երկու առարկա և այլն բաժանող տարածություն, ինչ-որ մեկի միջև եղած բացը, քան l. Ամենակարճ գետը երկու կետերի միջև. Տնից դպրոց Ռ. Նահանջ դեպի մոտակա գետ: Մեկ մետր հեռավորության վրա՝ ձեռքերը պարզած։ Ինչ-որ բան իմացիր, մի բան զգացիր: վրա… … Հանրագիտարանային բառարան

հեռավորությունը- Ես; տես. տես նաեւ հեռավորություն ա) Երկու կետ, երկու առարկա և այլն բաժանող տարածություն, ինչ-որ մեկի միջև եղած բացը, քան l. Երկու կետերի միջև ամենակարճ հեռավորությունը: Հեռավորությունը տնից դպրոց. Նահանջ դեպի մոտ հեռավորություն / nee ... Բազմաթիվ արտահայտությունների բառարան

ԵՐԿՐԱՉԱՓՈՒԹՅՈՒՆ- մաթեմատիկայի ճյուղ, որն ուսումնասիրում է տարբեր ձևերի (կետեր, գծեր, անկյուններ, երկչափ և եռաչափ առարկաների) հատկությունները, դրանց չափը և հարաբերական դիրքը։ Դասավանդման հարմարության համար երկրաչափությունը բաժանվում է պլանաչափության և պինդ երկրաչափության։ AT…… Collier հանրագիտարան

Նավիգացիա*

Նավիգացիա- նավիգացիայի բաժին (տես), ամփոփելով ծովում նավի տեղը որոշելու ուղիների ներկայացում, օգտագործելով կողմնացույց և գերան (տես): Որոշել նավի տեղը ծովում, նշանակում է քարտեզի վրա դնել այն կետը, որտեղ գտնվում է նավը այս պահինգտնվում է…… Հանրագիտարանային բառարան Ֆ.Ա. Բրոքհաուսը և Ի.Ա. Էֆրոն

ՔՈԳԵՆ- (Կոհեն) Հերման (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. Անհավատալի է թվում, որ Յոկոհամա ծովային գծապատկերի վրա Պանամայի ջրանցքի հետ կապող կոր ուղին ավելի կարճ է, քան նույն կետերի միջև գծված ուղիղ գիծը։


    Հարցը պարզաբանելու համար պետք է մի քանի խոսք ասել գծապատկերների մասին ընդհանրապես և ծովային քարտեզների մասին՝ մասնավորապես։ Երկրի մակերևույթի մասերը թղթի վրա գծելն անգամ սկզբունքորեն հեշտ գործ չէ, քանի որ Երկիրը գնդիկ է, և հայտնի է, որ գնդաձև մակերեսի ոչ մի հատված չի կարող տեղակայվել հարթության վրա՝ առանց ծալքերի և ճեղքերի։ Ակամայից պետք է համակերպվել քարտեզների անխուսափելի աղավաղումների հետ։ Քարտեզներ գծելու բազմաթիվ եղանակներ են հորինվել, բայց բոլոր քարտեզները զերծ չեն թերություններից. ոմանք ունեն մի տեսակի աղավաղումներ, մյուսները՝ այլ, բայց առանց աղավաղումների քարտեզներ ընդհանրապես չկան։

    Նավաստիներն օգտագործում են 16-րդ դարի հին հոլանդացի քարտեզագրի և մաթեմատիկոսի մեթոդով գծված քարտեզներ։ Մերկատոր. Այս մեթոդը կոչվում է Մերկատորի պրոյեկցիա: Հեշտ է ճանաչել ծովային գծապատկերն իր ուղղանկյուն ցանցով. միջօրեականները ցուցադրվում են դրա վրա որպես զուգահեռ ուղիղ գծերի շարք; լայնության շրջաններ - նաև առաջինին ուղղահայաց ուղիղ գծերով (տես նկ. 5):

    Պատկերացրեք հիմա, որ դուք ցանկանում եք գտնել ամենակարճ ճանապարհը օվկիանոսի մի նավահանգստից մյուսը նույն զուգահեռի վրա: Օվկիանոսում բոլոր ուղիները հասանելի են, և միշտ հնարավոր է ճանապարհորդել այնտեղ ամենակարճ ճանապարհով, եթե գիտեք, թե ինչպես է այն գտնվում: Մեր դեպքում բնական է կարծել, որ ամենակարճ ճանապարհն անցնում է այն զուգահեռով, որի վրա ընկած են երկու նավահանգիստները. ի վերջո, քարտեզի վրա դա ուղիղ գիծ է, և ի՞նչ կարող է լինել ավելի կարճ, քան ուղիղ ճանապարհը: Բայց մենք սխալվում ենք. զուգահեռ ճանապարհը ամենևին էլ ամենակարճը չէ։

    Իրոք, գնդի մակերևույթի վրա երկու կետերի միջև ամենակարճ հեռավորությունը դրանք միացնող մեծ շրջանի աղեղն է: Բայց զուգահեռի շրջանակը փոքր շրջան. Մեծ շրջանագծի աղեղը ավելի քիչ կոր է, քան նույն երկու կետերով գծված ցանկացած փոքր շրջանի աղեղը. ավելի մեծ շառավիղը համապատասխանում է ավելի փոքր կորությանը: Քաշեք թելը գլոբուսի վրա մեր երկու կետերի միջև (տես նկ. 3); դուք կհամոզվեք, որ այն ընդհանրապես չի ընկած զուգահեռի երկայնքով: A Tight Thread - Անվիճելի ցուցիչ ամենակարճ ճանապարհըև եթե այն չի համընկնում երկրագնդի զուգահեռի հետ, ապա ծովային գծապատկերի վրա ամենակարճ ճանապարհը չի նշվում ուղիղ գծով. հիշեք, որ զուգահեռների շրջանակները նման քարտեզի վրա պատկերված են ուղիղ գծերով, ցանկացած գիծ, ​​որը ցույց է տալիս. չի համընկնում ուղիղ գծի հետ կոր .



    Բրինձ. 3. Երկու կետերի միջև իսկապես ամենակարճ ճանապարհը գտնելու պարզ միջոց. այս կետերի միջև պետք է թել քաշել երկրագնդի վրա:


    Ասվածից հետո պարզ է դառնում, թե ինչու է ծովային գծապատկերի ամենակարճ ճանապարհը պատկերված ոչ թե ուղիղ, այլ կոր գիծ։

    Նրանք ասում են, որ Նիկոլաևսկայայի համար ուղղություն ընտրելիս (այժմ Օկտյաբրսկայա) երկաթուղիկային անվերջ վեճեր այն մասին, թե ինչ ճանապարհով պետք է այն դնել։ Վեճերը վերջ դրվեցին Նիկոլայ I ցարի միջամտությամբ, ով խնդիրը բառացիորեն «ուղղակի» լուծեց. նա գծով Սանկտ Պետերբուրգը կապեց Մոսկվայի հետ։ Եթե ​​դա արված լիներ Մերկատորի քարտեզի վրա, ապա դա ամոթալի անակնկալ կլիներ. ուղիղ գծի փոխարեն ճանապարհը ոլորան կվերածվեր:

    Յուրաքանչյուրը, ով չի խուսափում հաշվարկներից, կարող է պարզ հաշվարկով համոզվել, որ քարտեզի վրա մեզ կորացած ուղին իրականում ավելի կարճ է, քան այն, որը մենք պատրաստ ենք ուղիղ համարել: Թող մեր երկու նավահանգիստները ընկնեն 60-րդ զուգահեռականի վրա և բաժանվեն 60° հեռավորությամբ։ (Արդյոք այդպիսի երկու նավահանգիստներ իրականում գոյություն ունեն, իհարկե, հաշվարկելու համար էական չէ):



    Բրինձ. 4. Գնդակի վրա A և B կետերի միջև հեռավորությունների հաշվարկը զուգահեռ աղեղի և մեծ շրջանի աղեղի երկայնքով


    Նկ. 4 միավոր Օ -կենտրոն երկրագունդը, AB -լայնության շրջանագծի կամարը, որի վրա գտնվում են նավահանգիստները A և B; մեջնրա 60 °. Լայնության շրջանագծի կենտրոնը գտնվում է մի կետում ԻՑՊատկերացրեք դա կենտրոնից Օերկրագնդի միևնույն նավահանգիստների միջով գծվում է մի մեծ շրջանաձև աղեղ՝ նրա շառավիղը OB = OA = R;այն մոտ կանցնի գծված աղեղին AB,բայց դա չի համընկնում:

    Եկեք հաշվարկենք յուրաքանչյուր աղեղի երկարությունը: Քանի որ կետերը ԲԱՅՑև ATընկած են 60° լայնության վրա, ապա շառավիղները ՕԱև ՕՎդիմահարդարվել հետ ՕՀ(երկրագնդի առանցքը) 30° անկյուն։ Ուղղանկյուն եռանկյունու մեջ ASOոտքը AC (=r), 30° անկյան դիմաց ընկածը հավասար է հիպոթենուսի կեսին ԲԲԸ;

    նշանակում է, r=R/2Աղեղի երկարությունը ԱԲլայնության շրջանագծի երկարության մեկ վեցերորդն է, և քանի որ այս շրջանագիծն ունի մեծ շրջանի երկարության կեսը (համապատասխանում է շառավիղի կեսին), ապա փոքր շրջանի աղեղի երկարությունը



    Այժմ նույն կետերի միջև գծված մեծ շրջանագծի աղեղի երկարությունը որոշելու համար (այսինքն՝ նրանց միջև ամենակարճ ճանապարհը), մենք պետք է իմանանք անկյան մեծությունը։ AOW.Ակորդ ԱՍ, հանելով աղեղը մինչև 60 ° (փոքր շրջան), նույն փոքր շրջանով գրված կանոնավոր վեցանկյունի կողմն է. Ահա թե ինչու AB \u003d r \u003d R / 2

    Ուղիղ գիծ նկարելը od,միացնող կենտրոն Օերկրագունդը՝ մեջտեղով Դակորդներ AB,ստացեք ուղղանկյուն եռանկյուն ODA,որտեղ է անկյունը Դ-ուղիղ:

    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. Երկրագնդի ծովային կամ Մերկատոր քարտեզ։ Նման քարտեզների վրա հասարակածից հեռու ուրվագծերի չափերը խիստ չափազանցված են։ Ո՞րն է, օրինակ, ավելի մեծ՝ Գրենլանդիան, թե՞ Ավստրալիան: (պատասխանը տեքստով)


    Նավաստիների նախասիրությունը Mercator քարտեզների նկատմամբ այժմ հասկանալի է: Ցանկանալով որոշել այն ընթացքը, որը պետք է հետևել նշանակված նավահանգիստ գնալիս՝ նավիգատորը կիրառում է քանոն ուղու վերջնակետերին և չափում այն ​​անկյունը, որը նա կազմում է միջօրեականների հետ: Այս ուղղությամբ մշտապես բաց ծովում մնալով՝ նավիգատորը նավը ճշգրիտ կհասցնի թիրախին։ Տեսնում եք, որ «լոքսոդրոմը» թեև ոչ ամենակարճն է և ոչ ամենատնտեսողը, բայց որոշակի առումով շատ հարմար ճանապարհ է նավաստի համար։ Օրինակ՝ Բարի Հույսի հրվանդանից մինչև Ավստրալիայի հարավային ծայրերը հասնելու համար (տես նկ. 1), պետք է միշտ պահպանել նույն ընթացքը S 87 °.50 "։ Մինչդեռ նավը նույն տեղում հասցնելու համար։ վերջնական կետ ամենակարճ ճանապարհը(ըստ «օրթոդրոմիայի»), անհրաժեշտ է, ինչպես երևում է նկարից, շարունակաբար փոխել նավի ընթացքը՝ սկսել S 42 °, 50 «ընթացքից և ավարտել N 53 °, 50 ընթացքով։ «(այս դեպքում ամենակարճ ճանապարհը նույնիսկ իրագործելի չէ. այն հենվում է Անտարկտիկայի սառցե պատի մեջ):

    Երկու ճանապարհներն էլ՝ «լոքսոդրոմի» և «օրթոդրոմի» երկայնքով, համընկնում են միայն այն դեպքում, երբ մեծ շրջանի երկայնքով ուղին պատկերված է ծովային գծապատկերում որպես ուղիղ գիծ՝ հասարակածի երկայնքով կամ միջօրեականի երկայնքով շարժվելիս: Մնացած բոլոր դեպքերում այս ուղիները տարբեր են։

    Դեյկստրայի ալգորիթմը գրաֆիկական ալգորիթմ է, որը հորինել է հոլանդացի գիտնական Էդսգեր Դեյկստրան 1959 թվականին։ Գտնում է գծապատկերի գագաթներից մեկից մինչև մնացած ամենակարճ ուղիները: Ալգորիթմն աշխատում է միայն բացասական քաշի եզրեր չունեցող գրաֆիկների համար:

    Դիտարկենք ալգորիթմի կատարումը նկարում ներկայացված գրաֆիկի օրինակով:

    Թող պահանջվի գտնել ամենակարճ հեռավորությունները 1-ին գագաթից մինչև մյուս բոլորը:

    Շրջանակները ցույց են տալիս գագաթները, գծերը ցույց են տալիս նրանց միջև եղած ուղիները (գրաֆիկի եզրերը): Շրջանակներում նշված են գագաթների թվերը, եզրերից վեր նշված է դրանց «գինը»՝ ճանապարհի երկարությունը։ Յուրաքանչյուր գագաթի կողքին նշվում է կարմիր պիտակ՝ գագաթ 1-ից դեպի այս գագաթ տանող ամենակարճ ճանապարհի երկարությունը:

    Առաջին քայլը. Դիտարկենք Դեյկստրայի ալգորիթմի մի քայլ մեր օրինակի համար: Գագաթ 1-ն ունի նվազագույն պիտակը: 2-րդ, 3-րդ և 6-րդ գագաթները նրա հարևաններն են:

    1-ին գագաթի առաջին հարևանն իր հերթին 2-րդ գագաթն է, քանի որ դրան տանող ճանապարհի երկարությունը նվազագույն է: 1-ին գագաթով դեպի իրեն տանող ճանապարհի երկարությունը հավասար է 1-ին գագաթի պիտակի արժեքի գումարին և 1-ից 2-րդ գնացող եզրի երկարությանը, այսինքն՝ 0 + 7 = 7: Սա փոքր է, քան 2-րդ գագաթի ընթացիկ պիտակը, անսահմանություն, ուստի 2-րդ գագաթի նոր պիտակը 7 է:

    Նմանատիպ գործողություն ենք կատարում 1-ին գագաթի երկու այլ հարեւանների հետ՝ 3-րդ և 6-րդ:

    Հանգույց 1-ի բոլոր հարեւանները ստուգվում են: Մինչև գագաթ 1 ներկայիս նվազագույն հեռավորությունը համարվում է վերջնական և ենթակա չէ վերանայման (այն փաստը, որ դա իսկապես այդպես է, առաջին անգամ ապացուցվել է Է. Դեյկստրայի կողմից): Անջատեք այն գրաֆիկից դուրս՝ նշելու, որ այս գագաթն այցելել է:

    Երկրորդ քայլ. Ալգորիթմի քայլը կրկնվում է: Կրկին մենք գտնում ենք չայցելված գագաթներից «ամենամոտը»: Սա 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], count, index, i, u, m=st+1; bool visited[V]; for (i= 0 ես "< "<> "; cin>>սկիզբ; Dijkstra (GR, սկիզբ-1); համակարգ ("դադար>>անվավեր"); )

    Պասկալ

    ծրագիր DijkstraAlgorithm; usecrt; constV=6; inf=100000; տեսակ վեկտոր=ամբողջ թվի զանգված; 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(GR. ամբողջ թվերի զանգված; st. ամբողջ թիվ); var count, ինդեքս, i, u, m, min՝ ամբողջ թիվ; հեռավորությունը՝ վեկտոր; այցելած՝ բուլյան զանգված; սկիզբ:=st; համար i:=1-ից V սկսել հեռավորությունը[i]:=inf; այցելած[i]:=կեղծ; վերջ; հեռավորությունը:=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) և (distance[u]+GR inf then writeln(m," > ", i," = ", հեռավորություն[i]) else writeln(m," > ", i," = ", "երթուղին անհասանելի է"); վերջ; (հիմնական ծրագրի բլոկ) սկսել clrscr; write("Սկսվող հանգույց >>"); կարդալ (սկիզբ); Dijkstra (GR, սկիզբ); վերջ.

    Java

    ներմուծել java.io.BufferedReader; ներմուծել java.io.IOException; ներմուծել java.io.InputStreamReader; ներմուծել java.io.PrintWriter; ներմուծել java.util.ArrayList; ներմուծել java.util.Arrays; ներմուծել java.util.StringTokenizer; հանրային դաս Լուծում ( մասնավոր ստատիկ int INF = Integer.MAX_VALUE / 2; մասնավոր int n; // գագաթների թիվը երկգրաֆում մասնավոր int m; // աղեղների թիվը երկգրաֆում մասնավոր ArrayList adj; //հարակից ցուցակ մասնավոր ArrayList քաշը; //օգտագործված եզրի կշիռը երկգրաֆի մասնավոր բուլյանում; //զանգված՝ անցած և չանցած գագաթների մասնավոր int dist-ի մասին տեղեկատվության պահպանման համար; //զանգված՝ սկզբնական գագաթից հեռավորությունը պահպանելու համար //նախնիների զանգված, որն անհրաժեշտ է սկզբնական գագաթից ամենակարճ ճանապարհը վերականգնելու համար private int pred; int start; //մեկնարկային գագաթ, որտեղից որոնվում է բոլոր մյուսների հեռավորությունը private BufferedReader cin; մասնավոր PrintWriter cout; մասնավոր StringTokenizer նշանաբան; //Dijkstra-ի ալգորիթմը մեկնարկային գագաթից մասնավոր void dejkstra(int s) սկսելու կարգը ( dist[s] = 0; //սկզբնական գագաթից ամենակարճ հեռավորությունը 0-ի համար է (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]; համար (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 = ( նոր 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), ); մասնավոր ստատիկ վերջնական String START = «a»; մասնավոր ստատիկ վերջնական տող END = «e»; հանրային ստատիկ դատարկ հիմնական (String args) ( Graph g = նոր գրաֆիկ (GRAPH); g.dijkstra (START); g.printPath(END); //g.printAllPaths(); ) ) դասի գրաֆիկ ( մասնավոր վերջնական քարտեզ գրաֆիկ; // Vertex անվանումների քարտեզագրում Vertex օբյեկտներին, որը կառուցված է եզրերի մի շարքից /** Գրաֆիկի մեկ եզրը (օգտագործվում է միայն Graph կառուցողի կողմից) */ public static class Edge (public final String v1, v2; public final int dist; public Edge(String v1, String v2, int dist) ( this.v1 = v1; this.v2 = v2; this.dist = dist; ) ) /** Գրաֆիկի մեկ գագաթ՝ լրացված հարևան գագաթների քարտեզագրմամբ */ հանրային ստատիկ դասի Vertex-ը իրականացնում է Համեմատելի (Հանրային վերջնական տողի անունը; հանրային 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) ( graph = new HashMap<>(եզրեր.երկարություն); //մեկ անցում` գտնելու բոլոր գագաթները (Edge e: եզրեր) ( if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph. containKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); ) //մեկ այլ անցում սահմանելու հարեւան գագաթները (Edge e: եզրեր) ( 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("Graph does not պարունակում է սկզբնական գագաթ \"%s\"\n", startName); վերադարձ; ) վերջնական գագաթի աղբյուր = graph.get(startName); NavigableSet q = նոր TreeSet<>(); // գագաթների տեղադրում (Վերտեքս v: graph.values()) (v.նախորդ = v == աղբյուր ? աղբյուր՝ null; v.dist = v == աղբյուր ? 0: Integer.MAX_VALUE; q.add( v);) dijkstra(q); ) /** Dijkstra-ի ալգորիթմի իրականացում` օգտագործելով երկուական կույտ: */ private void dijkstra(final NavigableSet) q) ( Vertex u, v; while (!q.isEmpty()) (u = q.pollFirst(); // գագաթը ամենակարճ հեռավորությամբ (առաջին կրկնությունը կվերադարձնի աղբյուրը), եթե (u.dist == Integer.MAX_VALUE) ընդմիջում; // մենք կարող ենք անտեսել u (և մնացած ցանկացած այլ գագաթներ), քանի որ դրանք անհասանելի են //նայել հեռավորությունները յուրաքանչյուր հարևանի համար (Map.Entry) ա.< 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(); } } }

    Գ

    #ներառում #ներառում #ներառում //#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 *եզր; /* եզակի կապակցված եզրերի ցանկ */ 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->եզր; a->եզր = e_next; ) void free_edges() ( (; edge_root; edge_root = e_next) (e_next = edge_root.sibling; free(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 */ համար (; i > 1 && nd->dist< heap->հեռավորություն; i = j) (կույտ[i] = կույտ[j])->կույտ_idx = i; կույտ[i] = nd; nd-> heap_idx = i; ) node_t * pop_queue () ( node_t *nd, *tmp; int i, j; եթե (!heap_len) վերադարձնում է 0; /* հեռացնել առաջատար տարրը, քաշել պոչ տարրը այնտեղ և downheap */ nd = կույտ; tmp = կույտ; համար (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; (կույտ[i] = կույտ[j])->կույտ_idx = i; ) կույտ[i] = tmp; tmp-> heap_idx = i; վերադարձ nd; ) /* --- Dijkstra stuff; անհասանելի հանգույցներ երբեք չեն ստեղծի մեջհերթ --- */ 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(unreached)", nd->name); else ( show_path(nd->via); printf("- > %s(%g) ", nd->name, nd->dist); ) ) int main(void) ( #ifndef BIG_EXAMPLE int i; # սահմանել 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; $previous[$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 as pp inf = float("inf") Edge = namedtuple("Edge", "start, end, cost") class Graph(): def __init__(self, edges): self .edges = edges2 = self.vertices = set(sum(( e-ի համար եզրերում2), )) def dijkstra(self, source, dest): պնդել աղբյուրը self.vertices dist = (գագաթ՝ inf գագաթի համար self.vertices-ում ) նախորդ = (գագաթ. Ոչ մեկը գագաթի համար self.vertices) dist = 0 q = self.vertices.copy() հարեւաններ = (գագաթ՝ set() գագաթի համար self.vertices) սկզբի, ավարտի, ինքնարժեքի համար: եզրեր՝ հարեւաններ.add((վերջ, ծախս)) #pp(հարեւաններ) մինչդեռ q: u = min(q, key=lambda գագաթ՝ 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"]