Поиск путей в графе — это нахождение оптимального пути между заданными вершинами графа.
Введение
Граф — это набор вершин (точек), которые могут соединяться отрезками прямых или, по-другому, рёбрами. Граф называется связным, если из любой его точки возможно проложить путь по рёбрам до любой другой точки.
Под циклом понимается выбранный маршрут по рёбрам графа, который начинается и заканчивается в одной точке.
Граф носит название взвешенного, кода каждое ребро имеет свой вес, то есть ему поставлено в соответствие числовое значение. Невозможно, чтобы два ребра соединяли одни и те же точки.
Существует много алгоритмов нахождения минимального пути внутри взвешенного связного графа. Самым коротким путём между двумя вершинами графа будет маршрут по рёбрам, при котором суммарный вес рёбер будет минимальным. В качестве примера практического применения графов можно привести вариант, когда нужно переехать из одного города в другой по кратчайшему пути. Существует несколько дорог между городами и каждая имеет свою длину.
На языке графов это задача о самом коротком маршруте, то есть поиске кратчайшего маршрута между точками графа или минимизация суммарного весового показателя рёбер, из которых состоит маршрут. Задача о самом коротком маршруте считается самой важной основополагающей задачей теории графов. В исходном (старом варианте) она звучит как задача о дилижансе. Важность этой задачи видна из её разных практических реализаций. К примеру, в навигаторах, работающих на основе GPS, выполняется нахождение маршрута минимальной длины между двумя перекрёстками. Вершинами графа в этом случае считаются перекрёстки, а рёбрами будут дороги, соединяющие перекрёстки. Когда суммарная длина пути между перекрёстками станет самой маленькой, то это значит, что найден оптимальный путь движения.
Постановка задачи поиска минимального пути
Проблема нахождения самого короткого пути на графе существует для случаев ориентированного, неориентированного и смешанного графов. Рассмотрим постановку задачи в наиболее простом варианте для неориентированного графа. При рассмотрении случая ориентированного или смешанного графа, необходимо ещё учесть в каких направлениях расположены рёбра графа.
Две точки (вершины) графа считаются смежными, если у них есть общее ребро, соединяющее их.
Маршрут или путь внутри неориентированного графа является последовательным набором вершин (точек). Существует функция веса, отображающая рёбра с их весами, и неориентированный граф. Тогда минимальным путём из одной вершины в другую будет считаться путь, имеющий минимальную сумму. В случае, когда у всех рёбер одинаковый вес, тогда целью становится минимизация числа рёбер, которые надо пройти по маршруту.
Задача определения минимального пути может быть поставлена в следующих вариантах:
- Нахождение кратчайшего маршрута к заданному пункту назначения. Необходимо сформировать самый короткий путь к пункту назначения, вершине t. Начало пути может быть в любой из вершин графа, кроме t. Если изменить направление всех рёбер графа, то задача сводится к задаче о единой начальной точке и в ней надо найти минимальный путь из исходной точки во все остальные.
- Нахождение минимального маршрута между определённой парой точек. То есть необходимо определить самый короткий путь из точки U в точку V.
- Нахождение минимального маршрута между всеми парами вершин. То есть надо определить самый короткий путь из каждой точки U в каждую точку V. Такую задачу возможно разрешить при помощи алгоритма, который предназначен для задачи с одной начальной точкой, но есть возможность решить её быстрее.
В разных постановочных вариантах, в качестве веса ребра могут фигурировать не только меры длины, но и цена, временные интервалы, ресурсы и так далее. Или иные параметры, которые могут быть связаны с преодолением всех рёбер пути. Это означает, что задача может быть использована в самых разных научных сферах (информатике, экономике, географии и других). Но бывают случаи, когда при решении задачи о минимальном маршруте, требуется учесть различные ограничивающие факторы.
При их учёте, есть вероятность существенного усложнения задачи, например:
- Требуется найти самый короткий маршрут, который проходит через заданные точки. Здесь возможно сформулировать такие ограничивающие факторы: самый короткий путь должен пройти через выделенные точки, и самый короткий путь содержит минимальное число невыделенных точек.
- Требуется найти самый короткий маршрут, но при минимальном покрытии точек ориентированного графа путями.
- Необходимо определить самое маленькое по мощности количество путей.
- Необходимо найти минимальное по количеству маршрутов подмножество всех маршрутов, но при этом каждая дуга должна принадлежать хотя бы одному из них.
Алгоритмы поиска путей в графе
Так как есть много разных постановок этой задачи, то, соответственно, существуют различные алгоритмы нахождения самого короткого маршрута на графе:
- Согласно алгоритму Дейкстры возможно найти самый короткий маршрут из одной точки на графе ко всем остальным точкам. Этот алгоритм справедлив лишь для графов, которые не имеют рёбер с отрицательным весом.
- Используя алгоритм Беллмана – Форда можно определить самый короткий маршрут от одной точки графа ко всем другим точкам во взвешенном графе. В данном случае рёбра могут иметь отрицательный вес.
- Алгоритм поиска по определению маршрута с минимальной ценой перемещения от одной точки (исходной) к конечной. Применяется поисковый алгоритм по первому самому лучшему совпадению на графе.
- Применение алгоритма Флойда — Уоршелла позволяет найти самый короткий маршрут между всеми точками взвешенного ориентированного графа.
- Использование алгоритма Джонсона позволяет найти самый короткий маршрут между всеми парами точек взвешенного ориентированного графа.
- Волновой алгоритм Ли базируется на способе выполнения поисковых операций в ширину. Определяется путь между точками графа, который содержит минимум промежуточных точек или рёбер.
