Пути в графах

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

Задача 5. Предположим, что вам необходимо иметь в своем распоряжении автомобиль в течение нескольких лет. Имеется большой выбор автомобилей. Автомобили имеют различные сроки эксплуатации и разную стоимость. Каким образом на заданном временном интервале выбрать вариант покупок автомобилей, имеющий минимальную суммарную стоимость покупаемых автомобилей?

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

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

В данной главе будет рассмотрен алгоритм Дейкстры - алгоритм поиска кратчайшего пути в орграфе с неотрицательными весами. Причем к таким графам сводятся многие типы графов. Так, псевдоорграф превращается в орграф путем отбрасывания петель и заменой каждого множества кратных дуг кратчайшей дугой из этого множества. Если граф не ориентирован, то можно просто рассматривать граф, который получается из данного заменой каждого неориентированного ребра { i, j } парой дуг (i, j) и (j, i) с весом, равным весу исходного неориентированного ребра. Если граф не взвешен, можно считать, что все рёбра имеют один и тот же вес. Также здесь будет рассмотрен алгоритм поиска кратчайшего пути между каждой парой вершин исходного графа (алгоритм Флойда).