Кратчайший путь

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

Рассмотрим задачу № 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:

Таким образом, мы построили дерево, которое учитывает все возможные пути. Некоторые ветки дерева (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 построены дороги, протяженность которых приведена в таблице. Отсутствие числа в ячейке таблицы означает, что прямой дороги между пунктами нет.