Определите длину кратчайшего пути между пунктами

Определите длину кратчайшего пути между пунктами

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

Рассмотрим задачу № 3 из демонстрационного варианта ГИА

Между населенными пунктами A, B, C, D, Eпостроены дороги, протяженность которых приведена в таблице. Определите кратчайший путь между пунктами Aи D(при условии, что передвигаться можно только по построенным дорогам).

Уточним, что на самом деле в задаче требуется определить не сам кратчайший путь (последовательность ребер), а его длину. В условии дано еще 4 варианта ответа, но в данном случае они только мешают, поэтому мы их не приводим. Хотя задача сформулирована как практическая, она сводится к поиску кратчайшего пути в графе.

Способ 1.Построение графа.

По заданной таблице (весовой матрице графа) определяем, что граф содержит 7 ребер: AB(длиной 2), AC(4), AE(6), BC(1), CD(5), CE(1) и DE(3).

Нарисуем граф, соответствующий этим данным (вершины можно располагать как угодно):

Теперь перебираем все возможные пути из вершины Aв вершину D, не проходящие дважды через одну и ту же вершину, и считаем их длины:

ABCD: 2 + 1 + 5 = 8

ABCED: 2 + 1 + 1 + 3 = 7

ACD: 4 + 5 = 9

ACED: 4 + 1 + 3 = 8

AECD: 6 + 1 + 5 = 12

AED: 6 + 3 = 9

Чтобы не запутаться и не потерять какой-то путь, мы сначала рассмотрели все пути, начинающиеся с ребра AB, затем — все пути, начинающиеся с ребра AC, и т.д. Более того, пути перебираются в так называемом лексикографическом порядке, то есть в таком порядке, в каком они были бы расположены в словаре (в данном случае — в английском). Такой порядок делает перебор систематическим и поэтому уменьшает вероятность пропуска какого-то пути.

Сравнивая полученные длины, находим, что кратчайший путь ABCED(он выделен красным цветом) имеет длину 7:

Читайте также:  Как разложить сиденья в

Прелесть этого способа состоит в том, что в простых задачах можно сразу увидеть ответ, перебрав все варианты в уме и таким образом сэкономив время. Однако при этом есть риск пропустить какой-то вариант (на это и рассчитаны отвлекающие варианты ответов — дистракторы).

Способ 2.Построение дерева возможных путей.

Можно использовать другой способ, при котором явно строится схема возможных путей в графе (структура типа “дерево”). Сначала по таблице определяем, что из исходной вершины Aможно ехать только в B, Cи E:

Числа около стрелок обозначают длины дорог (веса соответствующих ребер), а числа около вершин — расстояния от начальной вершины Aпо этому пути.

Далее рассматриваем все пути, состоящие из двух ребер: из Bможно ехать в C(или вернуться в A, но такой вариант нас не интересует), из C— в B, Dи Е, а из E— в Си D. Однако первый же из рассмотренных путей, ABC, имеет длину 3, что меньше, чем длина ребра AC(4). Поэтому все пути, начинающиеся с ребра AC, можно далее вообще не рассматривать — в любом случае переезд из Ав Cчерез Bбудет на 1 короче, чем напрямую. По этой же причине не нужно рассматривать пути, начинающиеся с AEC(длина этого пути равна 7, что больше уже известного пути в Cдлиной 3):

Итак, мы нашли один путь (AED) из Aв D, который имеет длину 9. Пока запоминаем его, однако нужно рассмотреть еще ветку ABC, которая может дать более короткий путь.

По таблице находим, что из Cможно ехать в B, Dи E. Возвращаться в Bнет смысла, поэтому рассматриваем последние два варианта:

Получаем еще один (лучший на данный момент!) путь ABCDиз Aв Dдлиной 8. С другой стороны, длина пути ABCEменьше, чем длина предыдущего известного пути из Aв E(путь AE, длина 6), поэтому на этой ветке, возможно, удастся еще улучшить результат. И действительно, из Eимеет смысл ехать только в D(возвращаться в Aили в Cне стоит), и этот путь имеет длину 7:

Читайте также:  Калибровка джойстика в windows 10

Таким образом, мы построили дерево, которое учитывает все возможные пути. Некоторые ветки дерева (ACи AEC) отсечены, потому что эти пути заведомо не улучшают результат. Длина кратчайшего пути ABCEDравна 7.

Способ 3.Перебор возможных путей без построения

Сначала выпишем все ребра, соединяющие начальную вершину Aс другими вершинами, и их длины:

AB: 2

AC: 4

AE: 6

Теперь рассмотрим все пути, состоящие из двух ребер. Получив путь ABCдлиной 3, сразу отбрасываем все пути, проходящие через ребро AC(так же, как в способе 2):

ABC: 2 + 1 = 3

AEC: 6 + 1 = 7

AED: 6 + 3 = 9 (цель достигнута)

Видим, что все пути, проходящие через AEC, тоже можно отбросить. Остается проверить ветку ABC:

ABCD: 3 + 5 = 8 (цель достигнута)

ABCE: 3 + 1 = 4

Продолжая последнюю оставшуюся ветку ABCE, находим:

ABCED: 4 + 3 = 7 (цель достигнута)

Нерассмотренных путей, которые могли бы улучшить решение, больше не осталось, поэтому выбираем лучший путь: ABCEDдлиной 7.

Задачи для тренировки

Между населенными пунктами A, B, C, D, E, Fпостроены дороги, протяженность которых приведена в таблице. Отсутствие числа в ячейке таблицы означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами Aи F(при условии, что передвигаться можно только по построенным дорогам).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 10237 — | 7929 — или читать все.

Между населёнными пунк­та­ми А, В, С, D, Е по­стро­е­ны дороги, протяжённость ко­то­рых (в километрах) при­ве­де­на в таблице:

Определите длину крат­чай­ше­го пути между пунк­та­ми А и E. Пе­ре­дви­гать­ся можно толь­ко по дорогам, протяжённость ко­то­рых ука­за­на в таблице.

Найдём все ва­ри­ан­ты марш­ру­тов из A в E и вы­бе­рем самый короткий.

Из пунк­та A можно по­пасть в пунк­ты B, С.

Из пунк­та B можно по­пасть в пунк­ты C, D.

Читайте также:  Сколько заряжать аккумуляторные батарейки gp 2100

Из пунк­та C можно по­пасть в пункт D.

Из пунк­та D можно по­пасть в пункт E.

A—B—C—D—E: длина марш­ру­та 13 км.

A—B—D—E: длина марш­ру­та 10 км.

A—C—D—E: длина марш­ру­та 10 км.

A—C—B—D—E: длина марш­ру­та 9 км.

Самый ко­рот­кий путь: A—C—B—D—E. Длина марш­ру­та 9 км.

Задание 3. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

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

Из рисунка видно, что кратчайшее расстояние между пунктами A и F – это маршрут ABCEF с длиной 4+3+7+6=20.

Ссылка на основную публикацию
Обои для wallpaper engine девушки
Обои в аниме стиле, немного откровенные но эти обои понравятся фанатам стиля Аниме. Описание обоев, влияние на производительность, детали для...
Номер партийного билета единая россия
ПОЛОЖЕНИЕ о порядке изготовления, выдачи, хранения, использования и замены партийных членских билетов 1. Общие положения 1.1. В соответствии с п....
Обновить ключи для нод 32 бесплатно свежие
Вы находитесь на неофициальном сайте NOD32. Вы попали сюда потому, что ищете ключи для NOD32 Smart Security или NOD32 Антивирус....
Ожидание кэша что это значит
KOGDATA.RU — Многие способы отключение кэша либо не работают, либо делают это не так, как хочет пользователь. Когда "ожидание кэша"...
Adblock detector