Кратчайший путь на земле и на карте. Определение расстояния между двумя параллельными прямыми Кратчайшее расстояние между 2 точками

РАССТОЯНИЕ, расстояния, ср. 1. Пространство, разделяющее два пункта, промежуток между чем нибудь. Кратчайшее расстояние между двумя точками по прямой. Живет от нас на расстоянии двух километров. «Комендант подпустил их на самое близкое расстояние … Толковый словарь Ушакова

расстояние - сущ., с., употр. часто Морфология: (нет) чего? расстояния, чему? расстоянию, (вижу) что? расстояние, чем? расстоянием, о чём? о расстоянии; мн. что? расстояния, (нет) чего? расстояний, чему? расстояниям, (вижу) что? расстояния, чем? расстояниями … Толковый словарь Дмитриева

расстояние - я; ср. Пространство, разделяющее два пункта, два предмета и т.п., промежуток между кем, чем л. Кратчайшее р. между двумя точками. Р. от дома до школы. Отойти на близкое р. На расстоянии метра, вытянутой руки. Знать что л., чувствовать что л. на… … Энциклопедический словарь

расстояние - я; ср. см. тж. расстояньице а) Пространство, разделяющее два пункта, два предмета и т.п., промежуток между кем, чем л. Кратчайшее расстоя/ние между двумя точками. Расстоя/ние от дома до школы. Отойти на близкое расстоя/ние … Словарь многих выражений

ГЕОМЕТРИЯ - раздел математики, занимающийся изучением свойств различных фигур (точек, линий, углов, двумерных и трехмерных объектов), их размеров и взаимного расположения. Для удобства преподавания геометрию подразделяют на планиметрию и стереометрию. В… … Энциклопедия Кольера

Навигация*

Навигация - отдел кораблевождения (см.), заключающий изложение способов определения места корабля на море, пользуясь компасом и лагом (см.). Определить место корабля на море, значить нанести на карту ту точку, в которой корабль в данный момент находится.… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

КОГЕН - (Cohen) Герман (1842 1918) немецкий философ, основатель и виднейший представитель марбургской школы неокантианства. Основные работы: ‘Теория опыта Канта’ (1885), ‘Обоснование Кантом этики’ (1877), ‘Обоснование Кантом эстетики’ (1889), ‘Логика… …

Кант Иммануил - Жизненный путь и сочинения Канта Иммануил Кант родился в Кенигсберге (ныне Калининград) в Восточной Пруссии в 1724 г. Отец был шорником, а мать домохозяйкой, шестеро их детей не дожили до зрелого возраста. Кант всегда вспоминал родителей с… … Западная философия от истоков до наших дней

КРИТИЧЕСКАЯ ФИЛОСОФИЯ КАНТА: УЧЕНИЕ О СПОСОБНОСТЯХ - (La philosophie critique de Kant: Doctrines des facultes , 1963) работа Делеза. Характеризуя во введении трансцендентальный метод, Делез фиксирует, что Кант понимает философию как науку об отношении всякого знания к существенным целям… … История Философии: Энциклопедия

Ферма принцип - основной принцип геометрической оптики (См. Геометрическая оптика). Простейшая форма Ф. п. – утверждение, что луч света всегда распространяется в пространстве между двумя точками по тому пути, по которому время его прохождения меньше, чем … Большая советская энциклопедия

Путь по пунктирной линии на картинке короче, чем по сплошной. А теперь чуть чуть подробнее на примере морских маршрутов:

Если совершать плавание постоянным курсом, то траектория перемещения судна по земной поверхности будет представлять собой кривую, называемую в математике логарифмической спиралью.

В навигации эта сложная двоякой кривизны линия называется локсодромией , что в переводе с греческого языка означает «косой бег».

Однако кратчайшее расстояние между двумя точками на земном шаре измеряется по дуге большого круга.

Дуга большого круга получается как след от пересечения земной поверхности с плоскостью, проходящей через центр Земли, принимаемой за шар.

В навигации дуга большого круга получила название ортодромия , что в переводе означает «прямой бег». Второй особенностью ортодромии является то, что она пересекает меридианы под различными углами (рис. 29).

Разность расстояний между двумя точками на земной поверхности по локсодромии и ортодромии имеет практическое значение только при больших океанских переходах.

В обычных же условиях этой разностью пренебрегают и плавание совершают на постоянном курсе, т.е. по локсодромии.

Для вывода уравнения возьмем на локсодромии (рис. 30, а ) две точки А и В, расстояние между которыми элементарно мало. Проведя через них меридианы и параллель, получим элементарный прямоугольный сферический треугольник ABC. В этом треугольнике угол, образованный пересечением меридиана и параллели, прямой, а угол, P n AB равен курсу судна К. Катет АС представляет отрезок дуги меридиана и его можно выразить

где R - радиус Земли, принятой за шар;

Δφ - элементарное приращение широты (разность широт).

Катет СВ представляет отрезок дуги параллели

где r - радиус параллели;

Δλ - элементарная разность долгот.

Из треуголника OO 1 C можно найти, что

Тогда в окончательном виде катет СВ можно выразить так:

Принимая элементарный сферический треугольник ABC за плоский, напишем

После сокращения R и замены элементарно малых приращений координат бесконечно малыми будем иметь

Проинтегрируем полученное выражение в пределах от φ 1 , λ 1 до φ 2 , λ 2 считая значение tgK величиной постоянной:

В правой части имеем табличный интеграл. После подстановки его значения получим уравнение локсодромии на шаре

Анализ этого уравнения позволяет сделать следующие выводы:

При курсах 0 и 180° локсодромия превращается в дугу большого круга - меридиан;

При курсах 90 и 270° локсодромия совпадает с параллелью;

Локсодромия пересекает каждую параллель только один раз, а каждый меридиан - бесчисленное количество раз. т.е. спиралеобразно приближаясь к полюсу она его не достигает.

Плавание постоянным курсом, т. е. по локсодромии, хотя она и не является кратчайшим расстоянием между двумя точками на Земле, представляет для судоводителя значительные удобства.

Требования, предъявляемые к морской навигационной карте, можно сформулировать, основываясь на преимуществе плавания по локсодромии и результатах анализа ее уравнения следующим образом.

1. Локсодромия, пересекая меридианы под постоянным углом, должна изображаться прямой линией.

2. Картографическая проекция, используемая для построения карт, должна быть равноугольной, чтобы курсы, пеленги и углы на ней соответствовали своему значению на местности.

3. Меридианы и параллели, как линии курсов 0, 90, 180° и 270°, должны быть взаимно перпендикулярными прямыми линиями.

Кратчайшим расстоянием между двумя данными точками на поверхности Земли, принятой за шар, является меньшая из дуг большой окружности, проходящей через эти точки. Кроме случая следования судна по меридиану или экватору, ортодромия пересекает меридианы под разными углами. Поэтому судно, следующее по такой кривой, должно всё время изменять свой курс. Практически удобнее следовать по курсу, составляющему постоянный угол с меридианами и изображаемому на карте в проекции Меркатора прямой линией - локсодромией. Однако на больших расстояниях различие в длине ортодромии и локсодромии достигает значительной величины. Поэтому в таких случаях рассчитывают ортодромию и намечают на ней промежуточные точки, между которыми совершают плавание по локсодромии.

Картографическая проекция, удовлетворяющая перечисленным требованиям, была предложена голландским картографом Герардом Крамером (Меркатором) в 1569 г. В честь ее создателя проекция получила название меркаторской.

А кто хочет почерпнуть еще больше интересной информации узнайте подробнее Оригинал статьи находится на сайте ИнфоГлаз.рф Ссылка на статью, с которой сделана эта копия -

Наметив мелом две точки на классной доске, учительница предлагает юному школьнику задачу: начертить кратчайший путь между обеими точками.

Ученик, подумав, старательно выводит между ними извилистую линию.

– Вот так кратчайший путь! – удивляется учительница. – Кто тебя так научил?

– Мой папа. Он шофер такси.

Чертеж наивного школьника, конечно, анекдотичен, но разве не улыбнулись бы вы, если бы вам сказали, что пунктирная дуга на рис. 1 – самый короткий путь от мыса Доброй Надежды до южной оконечности Австралии!

Еще поразительнее следующее утверждение: изображенный на рис. 2 кружный путь из Японии к Панамскому каналу короче прямой линии, проведенной между ними на той же карте!

Рис. 1. На морской карте кратчайший путь от мыса Доброй Надежды до южной оконечности Австралии обозначается не прямой линией («локсодромией»), а кривой («ортодромией»)


Все это похоже на шутку, а между тем перед вами – бесспорные истины, хорошо известные картографам.




Рис. 2. Кажется невероятным, что криволинейный путь, соединяющий на морской карте Иокогаму с Панамским каналом, короче прямой линии, проведенной между теми же точками


Для разъяснения вопроса придется сказать несколько слов о картах вообще и о морских в частности. Изображение на бумаге частей земной поверхности – дело непростое даже в принципе, потому что Земля – шар, а известно, что никакую часть шаровой поверхности нельзя развернуть на плоскости без складок и разрывов. Поневоле приходится мириться с неизбежными искажениями на картах. Придумано много способов черчения карт, но все карты не свободны от недостатков: на одних имеются искажения одного рода, на других иного рода, но карт вовсе без искажений нет.

Моряки пользуются картами, начерченными по способу старинного голландского картографа и математика XVI в. Меркатора. Способ этот называется «меркаторской проекцией». Узнать морскую карту легко по ее прямоугольной сетке: меридианы изображены на ней в виде ряда параллельных прямых линий; круги широты – тоже прямыми линиями, перпендикулярными к первым (см. рис. 5).

Вообразите теперь, что требуется найти кратчайший путь от одного океанского порта до другого, лежащего на той же параллели. На океане все пути доступны, и осуществить там путешествие по кратчайшему пути всегда возможно, если знать, как он пролегает. В нашем случае естественно думать, что кратчайший путь идет вдоль той параллели, на которой лежат оба порта: ведь на карте – это прямая линия, а что может быть короче прямого пути! Но мы ошибаемся: путь по параллели вовсе не кратчайший.

В самом деле: на поверхности шара кратчайшее расстояние между двумя точками есть соединяющая их дуга большого круга. Но круг параллели – малый круг. Дуга большого круга менее искривлена, чем дуга любого малого круга, проведенного через те же две точки: большему радиусу отвечает меньшая кривизна. Натяните на глобусе нить между нашими двумя точками (ср. рис. 3); вы убедитесь, что она вовсе не ляжет вдоль параллели. Натянутая нить – бесспорный указатель кратчайшего пути, а если она на глобусе не совпадает с параллелью, то и на морской карте кратчайший путь не обозначается прямой линией: вспомним, что круги параллелей изображаются на такой карте прямыми линиями, всякая же линия, не совпадающая с прямой, есть кривая .



Рис. 3. Простой способ отыскания действительно кратчайшего пути между двумя пунктами: надо на глобусе натянуть нитку между этими пунктами


После сказанного становится понятным, почему кратчайший путь на морской карте изображается не прямой, а кривой линией.

Рассказывают, что при выборе направления для Николаевской (ныне Октябрьской) железной дороги велись нескончаемые споры о том, по какому пути ее проложить. Конец спорам положило вмешательство царя Николая I, который решил задачу буквально «прямолинейно»: соединил Петербург с Москвой по линейке. Если бы это было сделано на меркаторской карте, получилась бы конфузная неожиданность: вместо прямой дорога вышла бы кривой.

Кто не избегает расчетов, тот несложным вычислением может убедиться, что путь, кажущийся нам на карте кривым, в действительности короче того, который мы готовы считать прямым. Пусть обе наши гавани лежат на 60-й параллели и разделены расстоянием в 60°. (Существуют ли в действительности такие две гавани – для расчета, конечно, безразлично.)



Рис. 4. К вычислению расстояний между точками А и В на шаре по дуге параллели и по дуге большого круга


На рис. 4 точка О – центр земного шара, АВ – дуга круга широты, на котором лежат гавани А и В; в ней 60°. Центр круга широты – в точке С Вообразим, что из центра О земного шара проведена через те же гавани дуга большого круга: ее радиус OB = ОА = R; она пройдет близко к начерченной дуге АВ, но не совпадет с нею.

Вычислим длину каждой дуги. Так как точки А и В лежат на широте 60°, то радиусы ОА и ОВ составляют с ОС (осью земного шара) угол в 30°. В прямоугольном треугольнике АСО катет АС (=r), лежащий против угла в 30°, равен половине гипотенузы АО;

значит, r=R/2 Длина дуги АВ составляет одну шестую длины круга широты, а так как круг этот имеет вдвое меньшую длину, чем большой круг (соответственно вдвое меньшему радиусу), то длина дуги малого круга



Чтобы определить теперь длину дуги большого круга, проведенного между теми же точками (т. е. кратчайшего пути между ними), надо узнать величину угла АОВ. Хорда AS , стягивающая дугу в 60° (малого круга), есть сторона правильного шестиугольника, вписанного го в тот же малый круг; поэтому АВ = r=R/2

Проведя прямую OD, соединяющую центр О земного шара с серединой D хорды АВ, получаем прямоугольный треугольник 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’s algorithm) - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 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 using namespace std; const int V=6; //алгоритм Дейкстры void Dijkstra(int GR[V][V], int st) { int distance[V], count, index, i, u, m=st+1; bool visited[V]; for (i=0; i "< "<> "; cin>>start; Dijkstra(GR, start-1); system("pause>>void"); }

Pascal

program DijkstraAlgorithm; uses crt; const V=6; inf=100000; type vektor=array of integer; var start: integer; const GR: array of integer=((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)); {алгоритм Дейкстры} procedure Dijkstra(GR: array of integer; st: integer); var count, index, i, u, m, min: integer; distance: vektor; visited: array of boolean; begin m:=st; for i:=1 to V do begin distance[i]:=inf; visited[i]:=false; end; distance:=0; for count:=1 to V-1 do begin min:=inf; for i:=1 to V do if (not visited[i]) and (distance[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) and (distance[u]<>inf) and (distance[u]+GRinf then writeln(m," > ", i," = ", distance[i]) else writeln(m," > ", i," = ", "маршрут недоступен"); end; {основной блок программы} begin clrscr; write("Начальная вершина >> "); read(start); Dijkstra(GR, start); end.

Java

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { private static int INF = Integer.MAX_VALUE / 2; private int n; //количество вершин в орграфе private int m; //количествое дуг в орграфе private ArrayList adj; //список смежности private ArrayList weight; //вес ребра в орграфе private boolean used; //массив для хранения информации о пройденных и не пройденных вершинах private int dist; //массив для хранения расстояния от стартовой вершины //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины private int pred; int start; //стартовая вершина, от которой ищется расстояние до всех других private BufferedReader cin; private PrintWriter cout; private StringTokenizer tokenizer; //процедура запуска алгоритма Дейкстры из стартовой вершины 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(); } //считываем граф, заданный списком ребер for (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(); } }

Ещё один вариант:

Import java.io.*; import java.util.*; public class Dijkstra { private static final 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), }; private static final String START = "a"; private static final String END = "e"; public static void main(String args) { Graph g = new Graph(GRAPH); g.dijkstra(START); g.printPath(END); //g.printAllPaths(); } } class Graph { private final Map graph; // mapping of vertex names to Vertex objects, built from a set of Edges /** One edge of the graph (only used by Graph constructor) */ 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; } } /** One vertex of the graph, complete with mappings to neighbouring vertices */ public static class Vertex implements Comparable { public final String name; public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity public Vertex previous = null; public final Map neighbours = new 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(unreached)", 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); } } /** Builds a graph from a set of edges */ public Graph(Edge edges) { graph = new HashMap<>(edges.length); //one pass to find all vertices for (Edge e: edges) { if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); } //another pass to set neighbouring vertices for (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); // also do this for an undirected graph } } /** Runs dijkstra using a specified source vertex */ public void dijkstra(String startName) { if (!graph.containsKey(startName)) { System.err.printf("Graph doesn"t contain start vertex \"%s\"\n", startName); return; } final Vertex source = graph.get(startName); NavigableSet q = new TreeSet<>(); // set-up vertices for (Vertex v: graph.values()) { v.previous = v == source ? source: null; v.dist = v == source ? 0: Integer.MAX_VALUE; q.add(v); } dijkstra(q); } /** Implementation of dijkstra"s algorithm using a binary heap. */ private void dijkstra(final NavigableSet q) { Vertex u, v; while (!q.isEmpty()) { u = q.pollFirst(); // vertex with shortest distance (first iteration will return source) if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable //look at distances to each neighbour for (Map.Entry a: u.neighbours.entrySet()) { v = a.getKey(); //the neighbour in this iteration final 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

#include #include #include //#define BIG_EXAMPLE typedef struct node_t node_t, *heap_t; typedef struct edge_t edge_t; struct edge_t { node_t *nd; /* target of this edge */ edge_t *sibling;/* for singly linked list */ int len; /* edge cost */ }; struct node_t { edge_t *edge; /* singly linked list of edges */ node_t *via; /* where previous node is in shortest path */ double dist; /* distance from origining node */ char name; /* the, er, name */ int heap_idx; /* link to heap position for updating distance */ }; /* --- edge management --- */ #ifdef BIG_EXAMPLE # define BLOCK_SIZE (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif edge_t *edge_root = 0, *e_next = 0; /* Don"t mind the memory management stuff, they are besides the point. Pretend 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; e_next->sibling = a->edge; a->edge = e_next; } void free_edges() { for (; edge_root; edge_root = e_next) { e_next = edge_root.sibling; free(edge_root); } } /* --- priority queue stuff --- */ heap_t *heap; int heap_len; void set_dist(node_t *nd, node_t *via, double d) { int i, j; /* already knew better path */ if (nd->via && d >= nd->dist) return; /* find existing heap entry, or create a new one */ nd->dist = d; nd->via = via; i = nd->heap_idx; if (!i) i = ++heap_len; /* upheap */ for (; i > 1 && nd->dist < heap->dist; 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; if (!heap_len) return 0; /* remove leading element, pull tail element there and downheap */ nd = heap; tmp = heap; 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; return nd; } /* --- Dijkstra stuff; unreachable nodes will never make into the queue --- */ 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->sibling) set_dist(e->nd, lead, lead->dist + e->len); } void show_path(node_t *nd) { if (nd->via == nd) printf("%s", nd->name); else if (!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; # define N_NODES ("f" - "a" + 1) node_t *nodes = 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] = array("end" => $edge, "cost" => $edge); } $vertices = array_unique($vertices); foreach ($vertices as $vertex) { $dist[$vertex] = INF; $previous[$vertex] = NULL; } $dist[$source] = 0; $Q = $vertices; while (count($Q) > 0) { // TODO - Find faster way to get minimum $min = INF; foreach ($Q as $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";


Python

from collections import namedtuple, queue from pprint import 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(( for e in edges2), )) def dijkstra(self, source, dest): assert source in self.vertices dist = {vertex: inf for vertex in self.vertices} previous = {vertex: None for vertex in self.vertices} dist = 0 q = self.vertices.copy() neighbours = {vertex: set() for vertex in self.vertices} for start, end, cost in self.edges: neighbours.add((end, cost)) #pp(neighbours) while q: u = min(q, key=lambda vertex: dist) q.remove(u) if dist[u] == inf or u == dest: break for v, cost in neighbours[u]: alt = dist[u] + cost if 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"] (Начертательная геометрия)
  • CD (CXDX, C2D2) изображается в виде точки С5 = D5 А5В5 равно...
    (Начертательная геометрия)
  • Определение расстояния между двумя параллельными плоскостями
    Определение расстояния между двумя параллельными плоскостями общего положения 01| X удобно свести к задаче по определению расстояния между теми же двумя плоскостями, преобразованными в положение проецирующих. В этом случае расстояние между плоскостями определится как перпендикуляр между прямыми,...
    (Начертательная геометрия)
  • Определение расстояния между двумя скрещивающимися прямыми
    Если требуется определить кратчайшее расстояние между двумя скрещивающимися прямыми, приходится дважды менять системы плоскостей проекций. При решении этой задачи прямая CD (CXDX, C2D2) изображается в виде точки С5 = D5 (рис. 198). Расстояние от этой точки до проекции А5В5 равно...
    (Начертательная геометрия)
  • Угол между двумя скрещивающимися прямыми линиями
    Это угол между двумя пересекающимися прямыми, параллельными данным. Таким образом, эта задача аналогична предыдущей. Для ее решения нужно взять произвольную точку и через нее провести две прямые, параллельные заданным скрещивающимся прямым, и с помощью преобразования проекций определить искомый угол....
    (Основы начертательной геометрии. Краткий курс и сборник задач.)
  • Определение расстояния между двумя параллельными прямыми
    Задача решается способом двойной замены плоскостей проекций. На заключительном этапе одна из плоскостей проекций должна быть перпендикулярной к одной из скрещивающихся прямых. Тогда кратчайшее расстояние между ними определяется величиной отрезка перпендикуляра к другой скрещивающейся прямой (рис. 199)....
    (Начертательная геометрия)
  • КАТЕГОРИИ

    ПОПУЛЯРНЫЕ СТАТЬИ

    © 2021 «nemocafe.ru» — Игры и инструкции