2.4. Алгоритмы поиска путей

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

Примеры задач:

1. Несколько городов, в том числе AиB, связаны между собой сетью автомобильных дорог. Путешественник отправляется из городаAв городB. Какой маршрут он должен выбрать, чтобы добраться доB, проехав минимальное расстояние?

2. В условиях предыдущей задачи путешественник учитывает, что дороги между городами имеют различное покрытие, и, следовательно, для проезда по ним расход горючего и затраты на него являются различными. Поэтому он желает проехать в город Bс минимальными денежными затратами.

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

4. Несколько городов связаны между собой сетью коммуникационных линий связи. Каждая линия имеет ограниченную надежность, и для нее известна вероятность обеспечения нормальной связи. Фирма, расположенная в городе A, желает обеспечить с филиалом, расположенным в городеB, связь по наиболее надежному маршруту. Как его найти?

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

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

Предположим, что каждой дуге (i,j)ориентированного графа (случаи неориентированного или смешаного графа качественно ничем не отличаются, как будет видно из дальнейшего) поставлено в соответствие числоa_ij– длина дуги. (напомним, что понятие «длины» здесь условное,a_ij- просто какие-то действительные числа). Каждой паре узлов(i,j),для которых не существует дуги, соединяющих их, приписывается длинаa_ij=.Задача состоит в нахождении в данном графе такого пути из узлаsв узелt, для которого суммарная длина дуг минимальна.