Г
Р
А
Ф
Ы
Сеть дорог можно представить в виде графа с положительными весами. Вершины
являются дорожными развязками, а ребра дорогами, которые их соединяют. Веса ребер могут соответствовать
протяженности данного участка, времени необходимому для его преодоления или стоимости путешествия по нему.
Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например, автомагистрали). Она была формализована в понятии (идее) о магистралях.
Для реализации подхода, где одни дороги важнее других, существует множество алгоритмов. Они решают задачу поиска кратчайшего пути намного быстрее, чем аналогичные на обычных графах. Подобные алгоритмы состоят из двух этапов:
• этап предобработки. Производится предварительная обработка графа без учета начальной и конечной вершины. Обычно выполняется один раз и потом
используются полученные данные.
• этап запроса. Осуществляется запрос и поиск кратчайшего пути, при этом известны начальная и конечная вершина.
ПОИСК В ГРАФАХ
1. Поиск в глубину
Поиск в глубину стремится проникнуть подальше от исходной вершины.
Идея этого метода следующая. На каждом шагу метода:
•С текущей вершины движемся в первую вершину, смежную с текущей, в которой мы еще не были, если таковая имеется.
•Если таковой нет, то возвращаемся в вершину, с которой мы попали в текущую.
•Если же таковой нет и мы оказались в исходной вершине (возвращаться некуда), то это означает, что перебор вершин графа закончен.
ПОИСК В ГРАФАХ
2. Поиск в ширину
Этот алгоритм поиска в графе также
называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны.
Волна растекается равномерно во все стороны с одинаковой скоростью.
На i-ом шаге будут выписаны все вершины, достижимые за i ходов, если ходом считать
переход из одной вершины в другую. Метод поиска в ширину выходит из
программы поиска в глубину, если мы
заменим стек возврата на очередь.
Эта простая замена модифицирует порядок обхода вершин так, что обход идет равномерно во все стороны, а не внутрь как при поиске в
глубину.
Кратчайшим путем между двумя вершинами s и d в сети называется такой направленный простой путь из s в d, который имеет наименьший вес.
Задаа́ча о кратчаа́йшем пути— задача́
поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Значимость данной задачи определяется её различными практическими применениями. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между двумя перекрёстками. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Если сумма длин дорог между перекрёстками минимальна, тогда найденный путь самый короткий.