Решения

Постановка задачи о кратчайшем пути

В практических приложениях имеет большое значение задача о нахождении кратчайшего пути между двумя вершинами связного неориентированного графа.

Формулировка задачи может иметь несколько вариантов.

Вариант 1. Дана сеть автомобильных дорог, например, Тульской области. Найти кратчайшие пути от Тулы до каждого города области (если двигаться можно только по дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира. Для каждого известна стоимость. Найти маршрут минимальной стоимости (возможно с пересадками), например, из Торонто в Новосибирск.

Вариант 3. Есть план города с нанесенными на него местами расположения пожарных частей. Определить ближайшую к каждому дому пожарную станцию.

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

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

решения

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

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

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

1) начальной вершине присваивается индекс ;

2) всем вершинам, смежным с вершиной , присваиваем индекс 1;

3) всем вершинам, смежными с вершинами, имеющими индекс 1, присваиваем индекс 2, и так далее, пока не будет помечена вершина . Сам кратчайший путь найдем, если будем двигаться из конечной вершины в направлении убывания индексов.

На рис. 1 показаны индексы, которые получают вершины в процессе работы алгоритма. Так как вершина получила отметку 7, то длина кратчайшей цепи от до равна 7. Эта цепь выделена на рисунке.

Описанный алгоритм называют волновым, так как процесс расстановки отметок напоминает распространение возмущения, которое возникает в вершине и движется со скоростью одно ребро в единицу времени. Вершины, имеющие одинаковые отметки, представляют собой фронт волны.

Рис. 1. Отыскание кратчайшего пути в ненагруженном графе