왜 호 모양보다 직선 모양이 더 먼지 아시나요? 두 평행선 사이의 거리 결정 두 점 사이의 최단 거리는 얼마입니까?

그림에서 점선을 따라 가는 경로는 실선을 따라 가는 경로보다 짧습니다. 이제 해상 항로의 예를 사용하여 좀 더 자세히 설명합니다.

일정한 항로로 항해하면 배의 궤적은 지구의 표면수학에서 불리는 곡선이 될 것입니다 대수적나선.

내비게이션에서는 이 복잡한 이중 곡률선을 호출합니다. rhoxodrome, 그리스어로 번역하면 "비스듬한 달리기"를 의미합니다.

그러나 지구상의 두 지점 사이의 최단 거리는 대권의 호를 따라 측정됩니다.

대원의 호는 지구 표면과 공으로 간주되는 지구의 중심을 통과하는 평면의 교차점에서 추적으로 얻어집니다.

항해에서는 대권호(Great Circle Arc)라고 부른다. 교정술, 번역하면 "직선 실행"을 의미합니다. 정형술의 두 번째 특징은 경선과 다른 각도로 교차한다는 것입니다(그림 29).

록소드롬과 오르소드롬에 따른 지구 표면의 두 지점 사이의 거리 차이는 대규모 해양 횡단 중에만 실질적으로 중요합니다.

정상적인 조건에서는 이 차이가 무시되고 수영은 일정한 코스로 수행됩니다. rhoxodrome으로.

방정식을 도출하기 위해 rhoxodrome을 사용합시다 (그림 30, ㅏ) 두 점 ㅏ그리고 안에,그들 사이의 거리는 단순히 작습니다. 자오선과 평행선을 그리면 기본 직각 구형 삼각형을 얻습니다. 알파벳.이 삼각형에서는 자오선과 평행선이 이루는 각이 직각이고, 피NAB배의 방향과 동일 K. Katet 교류자오선 호의 세그먼트를 나타내며 표현될 수 있습니다.

어디 아르 자형 - 구로 간주되는 지구의 반경

Δψ - 위도의 기본 증분(위도의 차이).

다리 북동쪽평행한 호 세그먼트를 나타냅니다.

어디서 r - 평행 반경;

Δλ - 경도의 기본 차이.

삼각형 OO 1 C에서 그걸 찾을 수 있을 거야

그런 다음 최종 형태에서 다리 북동쪽다음과 같이 표현될 수 있습니다:

기본 구형 삼각형을 취함 알파벳플랫의 경우 다음과 같이 작성하겠습니다.

감소 후 아르 자형 그리고 기본적인 작은 좌표 증분을 무한한 좌표로 대체하면

결과식을 Φ1, λ1에서 Φ2까지의 범위에서 적분해 봅시다. λ 2 tgK 값이 일정하다고 생각하면:

오른쪽에는 테이블 일체형이 있습니다. 그 값을 대입한 후 공의 이형성 방정식을 얻습니다.

이 방정식을 분석하면 다음과 같은 결론을 내릴 수 있습니다.

0°와 180°의 코스에서 록소드롬은 대원호(자오선)로 변합니다.

90°와 270° 코스에서 rhoxodrome은 평행선과 일치합니다.

록소드롬은 각 평행선을 단 한 번만 교차하고 각 자오선은 무한한 횟수만큼 교차합니다. 저것들. 극을 향해 나선을 그리며 도달하지 못합니다.

일정한 코스, 즉 rhoxodrome을 따라 항해하는 것은 지구상의 두 지점 사이의 최단 거리가 아니지만 항해자에게 상당한 편의를 제공합니다.

해상항법도에 대한 요구사항은 rhoxodrome 항해의 장점과 그 방정식을 분석한 결과를 바탕으로 다음과 같이 공식화될 수 있다.

1. 자오선을 일정한 각도로 가로지르는 록소드롬은 직선으로 묘사되어야 합니다.

2. 지도 투영지도를 구성하는 데 사용되는 는 코스, 방위 및 각도가 지상에서의 의미와 일치하도록 등각이어야 합니다.

3. 0, 90, 180°, 270°의 코스선과 같이 자오선과 평행선은 서로 직교하는 직선이어야 한다.

구로 간주되는 지구 표면의 주어진 두 지점 사이의 최단 거리는 이 지점을 통과하는 대권의 호 중 더 작은 것입니다. 자오선이나 적도를 따라가는 선박의 경우를 제외하고, 정경은 자오선과 다른 각도로 교차합니다. 따라서 그러한 곡선을 따라가는 선박은 끊임없이 항로를 변경해야 합니다. 실제로는 자오선과 일정한 각도를 이루고 메르카토르 투영의 지도에 직선(록소드롬)으로 표시되는 코스를 따르는 것이 더 편리합니다. 그러나 먼 거리에서는 오르토드롬과 록소드롬의 길이 차이가 상당한 값에 도달합니다. 따라서 이러한 경우에는 오르토드롬이 계산되고 중간 지점이 표시되며 그 사이에서 록소드롬을 따라 항해합니다.

위의 요구 사항을 충족하는 지도 제작 투영법은 1569년 네덜란드 지도 제작자 Gerard Cramer(Mercator)에 의해 제안되었습니다. 제작자를 기리기 위해 투영법의 이름은 메르카토리안

그리고 누가 더 많은 것을 배우고 싶나요? 흥미로운 정보더 찾아 봐 원문은 홈페이지에 있습니다 InfoGlaz.rf이 사본이 작성된 기사에 대한 링크 -

DISTANCE, 거리, 평균 1. 두 점을 나누는 공간, 어떤 것 사이의 틈. 직선상의 두 점 사이의 최단 거리. 그는 우리로부터 2km 떨어져 있습니다. "사령관님은 최대한 가까이 다가가도록 하셨습니다... 사전우샤코바

거리- 명사, p., 사용됨 종종 형태: (아니요) 뭐요? 거리가 멀다, 왜? 거리, (참조) 뭐? 거리, 뭐? 거리, 뭐에 대해? 거리에 대해; pl. 무엇? 거리, (아니) 뭐? 거리, 뭐? 거리, (알겠습니다) 뭐요? 거리, 뭐? 거리... Dmitriev의 설명 사전

거리- 나; 수요일 두 점, 두 물체 등을 구분하는 공간, 누구 사이의 간격, l보다. 가장 짧은 강 두 지점 사이. R. 집에서 학교까지. 가까운 강으로 이동합니다. 1 미터 거리에서 팔 길이. 뭔가를 알고, 뭔가를 느껴보세요. 에… 백과사전

거리- 나; 수요일 또한보십시오 거리 a) 두 점, 두 물체 등을 분리하는 공간, 그 사이의 간격, l보다. 두 점 사이의 최단 거리. 집에서 학교까지의 거리. 가까운 곳으로 이동하세요.. 다양한 표현의 사전

기하학- 다양한 도형(점, 선, 각도, 2차원 및 3차원 객체)의 속성, 크기 및 상대 위치를 연구하는 수학 분야입니다. 쉽게 가르치기 위해 기하학은 면적 측정법과 입체 측정법으로 구분됩니다. 안에… … 콜리어의 백과사전

항해*

항해- 나침반과 통나무(참조)를 사용하여 바다에서 선박의 위치를 ​​결정하는 방법에 대한 설명이 포함된 항해 부서(참조). 바다에서 배의 위치를 ​​결정한다는 것은 배가 있는 지점을 지도에 표시하는 것을 의미합니다. 이 순간위치.… 백과사전 F.A. 브록하우스와 I.A. 에프론

코헨- (Cohen) Hermann (1842 1918) 독일 철학자, 창시자이자 신칸트주의 마르부르크 학파의 가장 저명한 대표자. 주요 저서 : '칸트의 경험론'(1885), '칸트의 윤리의 정당화'(1877), '칸트의 미학의 정당화'(1889), '논리학...

칸트 임마누엘- 칸트의 생애와 저작 임마누엘 칸트는 1724년 동프로이센의 쾨니히스베르크(지금의 칼리닌그라드)에서 태어났다. 그의 아버지는 안구장사였고 어머니는 주부였으며, 자녀 중 6명은 성인이 될 때까지 살지 못했다. 칸트는 항상 그의 부모를 기억했다. 서양철학의 기원부터 현재까지

칸트의 비판철학: 능력의 교육- (칸트 철학 비판: 교수 교리, 1963) 들뢰즈의 작품. 서론에서 초월적 방법을 특징짓면서 들뢰즈는 칸트가 철학을 모든 지식과 본질적인 목표의 관계에 대한 과학으로 이해한다고 지적합니다. 철학사: 백과사전

농장 원리- 기하광학의 기본 원리(기하광학 참조) f.p.의 가장 간단한 형태는 빛의 광선이 이동 시간이 다음보다 짧은 경로를 따라 두 지점 사이의 공간에서 항상 전파된다는 진술입니다. 큰 소련 백과사전

분필로 칠판에 두 점을 표시한 후 교사는 어린 남학생에게 두 점 사이의 최단 경로를 그리는 과제를 제공합니다.

학생은 생각한 후 조심스럽게 그들 사이에 구불구불한 선을 그립니다.

- 그게 가장 짧은 길이에요! – 선생님이 놀랐어요. - 그런 건 누가 가르쳤나요?

- 우리 아빠. 그는 택시 운전사입니다.

물론 순진한 남학생의 그림은 일화이지만, 그림에서 점선 호가 있다는 말을 들으면 웃지 않겠습니까? 1 - 희망봉에서 호주 남단까지의 최단 경로!

더욱 놀라운 것은 다음의 진술이다. 2 일본에서 파나마 운하까지의 우회 경로는 같은 지도에서 두 곳 사이를 그은 직선보다 짧습니다!

쌀. 1. 켜기 바다 지도희망봉에서 호주 남단까지의 최단 경로는 직선(“loxodrome”)이 아닌 곡선(“orthodrome”)으로 표시됩니다.

이 모든 것이 농담처럼 보이지만, 여러분 앞에는 지도 제작자에게 잘 알려진 확실한 진실이 있습니다.

쌀. 2. 해상 지도에서 요코하마와 파나마 운하를 연결하는 곡선 경로가 같은 지점을 이은 직선보다 짧다는 것은 놀라운 일입니다.

문제를 명확히 하기 위해 우리는 일반적인 지도와 특히 바다 지도에 대해 몇 마디 말해야 할 것입니다. 지구 표면의 일부를 종이에 그리는 것은 원칙적으로도 쉬운 일이 아닙니다. 지구는 공이기 때문에 구면의 ​​어떤 부분도 접히거나 찢어지지 않고 평면 위에 펼쳐질 수 없는 것으로 알려져 있습니다. 지도의 불가피한 왜곡은 필연적으로 참아야 합니다. 지도를 그리는 방법은 여러 가지가 있지만 모든 지도에는 단점이 있습니다. 어떤 지도에는 어떤 종류의 왜곡이 있고 어떤 지도에는 다른 종류가 있지만 왜곡이 전혀 없는 지도는 없습니다.

선원들은 16세기 고대 네덜란드 지도 제작자이자 수학자들의 방법에 따라 그려진 지도를 사용합니다. 메르카토르. 이 방법을 "메르카토르 투영법"이라고 합니다. 직사각형 격자로 바다 지도를 인식하는 것은 쉽습니다. 자오선은 일련의 평행한 직선으로 표시됩니다. 위도 원은 첫 번째 원에 수직인 직선이기도 합니다(그림 5 참조).

이제 동일한 평행선에 있는 한 항구에서 다른 항구까지의 최단 경로를 찾아야 한다고 상상해 보십시오. 바다에서는 모든 길이 접근 가능하며, 그것이 어떻게 흐르는지 알면 최단 경로를 따라 여행하는 것이 항상 가능합니다. 우리의 경우 최단 경로는 두 항구가 있는 평행선을 따라 간다고 생각하는 것이 당연합니다. 결국 지도에서 이 경로는 직선이고 직선 경로보다 더 짧을 수도 있습니다! 그러나 우리는 착각하고 있습니다. 병렬 경로는 전혀 최단 경로가 아닙니다.

실제로 공 표면에서 두 점 사이의 최단 거리는 두 점을 연결하는 대원호입니다. 그러나 평행선의 원 - 작은 원. 큰 원의 호는 동일한 두 점을 통해 그려진 작은 원의 호보다 덜 구부러집니다. 반경이 클수록 곡률이 작아집니다. 두 지점 사이에 지구본의 실을 늘립니다(그림 3 참조). 당신은 그것이 전혀 평행선을 따라 놓여 있지 않을 것이라고 확신하게 될 것입니다. 팽팽한 실은 확실한 지표입니다 최단 경로, 그리고 그것이 지구의 평행선과 일치하지 않으면 해상 지도에서 최단 경로는 직선으로 표시되지 않습니다. 평행선의 원은 지도에 직선으로 표시되지만 일치하는 모든 선은 직선과 일치하지 않는 것은 곡선 .

쌀. 3. 두 지점 사이의 실제 최단 경로를 찾는 간단한 방법: 두 지점 사이의 지구본에서 실을 당겨야 합니다.

이상의 설명을 듣고 나면 해상 지도에서 최단 경로가 직선이 아닌 곡선으로 표시되는 이유가 분명해집니다.

그들은 Nikolaevskaya (현재 Oktyabrskaya)의 방향을 선택할 때 다음과 같이 말합니다. 철도어떤 길을 택할지에 대한 끝없는 논쟁이있었습니다. 논쟁은 문자 그대로 "직접" 문제를 해결한 차르 니콜라스 1세의 개입으로 끝났습니다. 그는 상트페테르부르크와 모스크바를 선을 따라 연결했습니다. 만약 이것이 메르카토르 지도에서 이루어졌다면 결과는 당혹스러울 것입니다. 즉, 직선 도로 대신 도로가 구부러졌을 것입니다.

계산을 피하지 않는 사람이라면 누구나 간단한 계산을 통해 지도에서 우리에게 구부러진 것처럼 보이는 경로가 실제로 우리가 직선으로 간주할 준비가 되어 있는 경로보다 짧다는 것을 확인할 수 있습니다. 우리의 두 항구가 60도 평행선에 있고 60°의 거리로 분리되어 있다고 가정합니다. (물론 그러한 두 항구가 실제로 존재하는지 여부는 계산에 중요하지 않습니다.)

쌀. 4. 평행호와 대원호를 따라 공 위의 점 A와 B 사이의 거리를 계산하려면

그림에서. 4점 에 대한 -센터 지구, AB –항구가 위치한 위도권의 호 A와 B; V 60°입니다. 위도권의 중심은 점이다. 와 함께중앙에서 상상해보자 에 대한지구는 큰 원의 호에 의해 동일한 항구를 통해 그려집니다. 반경 OB = OA = R;그려진 호에 가깝게 지나갈 것입니다 AB,그러나 그것과 일치하지 않을 것입니다.

각 호의 길이를 계산해 봅시다. 포인트부터 ㅏ그리고 안에위도 60°, 반경 OA그리고 산부인과~에 달하다 OS(지구의 축) 각도는 30°입니다. 직각 삼각형에서 아소다리 AC(=r),빗변의 절반에 해당하는 30° 각도 반대편에 놓여 있음 JSC;

수단, r=R/2호 길이 AB는 위도원 길이의 1/6이고, 이 원은 큰 원 길이의 절반(반지름의 절반에 해당)을 가지므로 작은 원의 호 길이는

이제 같은 점들(즉, 두 점 사이의 최단 경로) 사이에 그려진 대원호의 길이를 결정하려면 각도의 크기를 알아야 합니다. AOB.현 처럼는 (작은 원의) 60° 호에 대응하며, 동일한 작은 원에 새겨진 정육각형의 변입니다. 그렇기 때문에 AB = r=R/2

직선을 그은 뒤 외경센터를 연결하다 에 대한중간이 있는 지구본 디화음 AB,우리는 직각삼각형을 얻습니다 ODA,각도는 어디에 있나요? 디 -똑바로:

DA= 1/2 AB 및 OA = R.

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

여기에서 우리는 (표에서) 다음을 찾습니다:

=14°28",5

따라서

= 28°57".

이제 필요한 최단 경로 길이를 킬로미터 단위로 찾는 것이 어렵지 않습니다. 지구의 대권의 1분 길이가 다음과 같다는 점을 기억하면 계산이 단순화될 수 있습니다.

우리는 해상 지도에 직선으로 표시된 위도권을 따른 경로가 3333km이고, 지도의 곡선을 따라 대권을 따르는 경로가 3213km, 즉 120km 더 짧다는 것을 알게 됩니다.

실로 무장하고 지구본을 가지고 있으면 그림의 정확성을 쉽게 확인하고 대원의 호가 그림에 표시된 대로 실제로 놓여 있는지 확인할 수 있습니다. 그림에 표시됩니다. 1 아프리카에서 호주까지의 "직선" 항로는 6020마일이고, "곡선" 항로는 5450마일, 즉 570마일, 즉 1050km 더 짧다고 합니다. 해상 지도에서 런던에서 상하이까지의 "직행" 항공로는 카스피해를 가로지르는 반면, 실제로 가장 짧은 경로는 상트페테르부르크 북쪽으로 운행됩니다. 이러한 문제가 시간과 연료를 절약하는 데 어떤 역할을 하는지는 분명합니다.

항해 시대에 항해 시간이 항상 중요하지 않은 경우 - "시간"이 아직 "돈"으로 간주되지 않았다면 증기선의 출현으로 과도하게 소비되는 석탄 1톤당 비용을 지불해야 합니다. 그렇기 때문에 오늘날 선박은 종종 메르카토르 투영이 아닌 소위 "중앙" 투영으로 만들어진 지도를 사용하여 가장 짧은 경로를 따라 안내됩니다. 이 지도에서는 ​​대원의 호가 직선으로 표시됩니다.

왜 초기 항해사들은 그러한 기만적인 지도를 사용하고 불리한 경로를 선택했습니까? 옛날에는 해도의 현재 표시된 특징을 몰랐다고 생각하는 것은 실수입니다. 물론 문제는 이것이 아니라 메르카토르 방법에 따라 그려진 지도가 불편함과 함께 선원들에게 매우 귀중한 이점을 가지고 있다는 사실로 설명됩니다. 이러한 지도는 먼저 윤곽의 각도를 유지하면서 왜곡 없이 지구 표면의 개별 작은 부분을 묘사합니다. 이는 적도에서 멀어질수록 모든 윤곽이 눈에 띄게 늘어난다는 사실과 모순되지 않습니다. 고위도에서는 스트레칭이 너무 커서 항해지도가 그 특징에 익숙하지 않은 사람에게 대륙의 실제 크기에 대한 완전히 잘못된 아이디어를 제공합니다. 그린란드는 아프리카와 같은 크기로 보이고 알래스카는 호주보다 큽니다. 아프리카보다 15배 작으며, 알래스카와 그린란드를 합하면 호주의 절반 크기입니다. 그러나 지도의 이러한 특징을 잘 알고 있는 선원은 이로 인해 오해를 받을 수 없습니다. 그는 특히 작은 지역 내에서 해도가 자연과 정확히 유사하기 때문에 이를 참았습니다(그림 5).

그러나 해도는 항해 연습 문제를 해결하는 데 큰 도움이 됩니다. 일정한 항로를 따라 이동하는 선박의 항로를 직선으로 표시한 유일한 지도이다. '일정한 길'을 걷는다는 것은 한 방향, 하나의 특정한 '기준점'을 일관되게 고수하는 것, 즉 모든 자오선을 동일한 각도로 교차하는 방식으로 걷는 것을 의미합니다. 그러나 이 경로(“loxodrome”)는 모든 자오선이 서로 평행한 직선인 지도에서만 직선으로 묘사될 수 있습니다. 그리고 지구상에서 위도원은 자오선과 직각으로 교차하므로, 그러한 지도에서 위도원은 자오선에 수직인 직선이어야 합니다. 간단히 말해서, 우리는 바다 지도의 특징을 구성하는 좌표 격자에 정확하게 도달합니다.

쌀. 5. 세계의 항해 또는 메르카토르 지도. 이러한 지도는 적도에서 멀리 떨어진 등고선의 크기를 크게 과장합니다. 예를 들어, 그린란드와 호주 중 어느 것이 더 큽니까? (텍스트로 답변)

메르카토르 지도에 대한 선원들의 선호는 이제 이해할 수 있습니다. 항해사는 지정된 항구로 갈 때 따라야 할 경로를 결정하기 위해 경로의 끝점에 자를 적용하고 자오선과 이루는 각도를 측정합니다. 이 방향으로 항상 넓은 바다를 유지하면 항해사는 배를 목표물까지 정확하게 가져올 것입니다. "loxodrome"은 비록 가장 짧지도 않고 가장 경제적이지도 않지만 어떤 면에서는 선원에게 매우 편리한 경로라는 것을 알 수 있습니다. 예를 들어, 희망봉에서 호주 남단까지 가려면(그림 1 참조) 항상 같은 항로 S 87°.50"에 머물러야 합니다. 동시에 배를 같은 결승에 진출시키려면 가리키다 최단 경로(“orthodrome”에 따라) 그림에서 볼 수 있듯이 선박의 경로를 지속적으로 변경하는 것이 필요합니다. S 42°.50" 코스에서 시작하고 N 53°.50 코스로 끝납니다. " (이 경우 최단 경로는 실현 가능하지도 않습니다. 남극의 얼음 벽에 놓여 있습니다.)

"loxodrome"을 따르는 경로와 "orthodrome"을 따르는 두 경로는 대권을 따르는 경로가 해상 해도에 직선으로 묘사되는 경우, 즉 적도 또는 자오선을 따라 이동할 때에만 일치합니다. 다른 모든 경우에는 이러한 경로가 다릅니다.

다익스트라 알고리즘(Dijkstra's Algorithm)은 네덜란드 과학자 Edsger Dijkstra가 1959년에 발명한 그래프 알고리즘이다. 그래프의 꼭지점 중 하나에서 다른 모든 꼭지점까지의 최단 경로를 찾습니다. 알고리즘이 작동합니다 음수 가중치의 간선이 없는 그래프에만 해당됩니다.

그림에 표시된 그래프의 예를 사용하여 알고리즘의 실행을 고려해 보겠습니다.

첫 번째 꼭지점에서 다른 모든 꼭지점까지의 최단 거리를 찾아야 한다고 가정해 보겠습니다.

원은 정점을 나타내고 선은 정점 사이의 경로(그래프의 가장자리)를 나타냅니다. 정점의 수는 원으로 표시되고 "가격"은 가장자리 위에 표시됩니다(경로의 길이). 각 정점 옆에는 빨간색 표시가 있습니다. 이는 정점 1에서 이 정점까지의 최단 경로 길이입니다.

첫 번째 단계. 예제에서 Dijkstra 알고리즘의 단계를 살펴보겠습니다. 정점 1에는 최소 레이블이 있으며, 이웃 정점은 정점 2, 3, 6입니다.

정점 1의 첫 번째 이웃은 정점 2입니다. 왜냐하면 정점 2로 가는 경로의 길이가 최소이기 때문입니다. 정점 1을 통과하는 경로의 길이는 정점 1의 레이블 값과 첫 번째에서 두 번째로 가는 가장자리의 길이의 합과 같습니다. 즉, 0 + 7 = 7입니다. 정점 2의 현재 레이블은 무한대이므로 새 레이블은 두 번째 정점은 7입니다.

우리는 첫 번째 꼭지점의 다른 두 이웃인 세 번째와 여섯 번째 정점에 대해서도 유사한 작업을 수행합니다.

정점 1의 모든 이웃이 확인됩니다. 정점 1까지의 현재 최소 거리는 최종적인 것으로 간주되며 수정될 수 없습니다(실제로 E. Dijkstra가 처음으로 입증한 경우입니다). 이 꼭지점을 방문했음을 표시하기 위해 그래프에서 줄을 그어 봅시다.

두번째 단계. 알고리즘 단계가 반복됩니다. 다시 우리는 방문하지 않은 정점 중 "가장 가까운" 정점을 찾습니다. 이는 레이블 7이 있는 정점 2입니다.

다시 우리는 선택된 정점의 이웃 레이블을 줄이고 두 번째 정점을 통과하려고 시도합니다. 정점 2의 이웃은 정점 1, 3, 4입니다.

정점 2의 첫 번째 (순서대로) 이웃은 정점 1입니다. 하지만 이미 방문한 적이 있으므로 첫 번째 정점에는 아무 작업도 수행하지 않습니다.

정점 2의 다음 이웃은 정점 3입니다. 왜냐하면 방문하지 않은 것으로 표시된 정점의 최소 레이블이 있기 때문입니다. 2를 통해 이동하면 해당 경로의 길이는 17(7 + 10 = 17)이 됩니다. 하지만 세 번째 정점의 현재 레이블은 9로 17보다 작으므로 레이블이 변경되지 않습니다.

정점 2의 또 다른 이웃은 정점 4입니다. 두 번째 정점을 통해 이동하면 해당 경로의 길이는 두 번째 정점까지의 최단 거리와 정점 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++