Что такое граф?
Граф – это математическая структура, которая помогает описывать отношения между объектами.
Он состоит из:
- Вершин – это точки (например, города).
- Рёбер – это линии, соединяющие вершины (например, дороги между городами).
Граф может быть:
- Ненаправленным, если связь между вершинами двусторонняя (например, дорога, по которой можно ехать в обе стороны).
- Направленным, если связь односторонняя (например, улица с односторонним движением).
Зачем искать кратчайший путь?
Представь, что ты хочешь доехать из одного города в другой. Чтобы не потратить лишнее время, важно найти маршрут, который будет самым коротким или удобным. Именно для этого мы используем алгоритмы поиска кратчайшего пути.
Поиск кратчайшего пути (перебор)
В заданиях ОГЭ этой темы используются таблицы.
Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
Примеры задач
Задачи будут двух типов: просто найти кратчайший путь либо найти кратчайший путь с заходом в определённую точку.
Задача №1
Между населёнными пунктами A, B, C, D построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
Решение:
Расставим точки, которые символизируют города, примерно по кругу.
Проведём дороги между городами так, как указано в таблице. Если на пересечении городов стоит число, значит, мы проводим линию между этими точками.
Поставим числа над каждой дорогой, характеризующие длины каждого отрезка.
Теперь найдём самый короткий путь из A в C.
Можно сразу попасть из A в C по прямой дороге за 8. Если пойдём через пункт D, то придём в город C за 7. Через город B так же можно прийти за 7 километров.
Но мы видим, что длина дороги из D в B равна 1. Попытаемся эту дорогу использовать при составлении маршрута. Получим путь: A-D-B-C. Получается 3+1+2=6. Это и есть искомый кратчайший путь.
Ответ: 6
Задача №2 ( С заходом в обязательный узел)
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице, два раза посещать один пункт нельзя.
Решение:
Расставим точки по кругу. Точка С - это обязательный пункт.
Проведём линии между городами так, как указано в задаче. Поставим числа над каждой дорогой, чтобы было понятно, к какой дороге конкретное число принадлежит.
Теперь можно начать искать кратчайший путь от A до E, проходящего через C.
Найдём кратчайший путь до точки С. Это и есть путь A-C. Он равен 5.
От С до E можно добраться разными путями:
C-E = 8
C-D-E = 2 + 5 = 7
C-B-E = 4 + 3 = 7
Видим длину BD = 1. Попытаемся использовать эту дорогу!
C-D-B-E = 2 + 1 + 3 = 6
Это и есть самый короткий путь.
В ответе напишем путь: A-C-D-B-E = 5 + 6 = 11.
Ответ: 11
Заключение
Сами по себе задание №4 несложное. Нужно просто внимательно перенести данные с таблицы в схему, и найти самый короткий путь.