Нахождение кратчайшего пути с помощью графов

Спицына Татьяна, группа А-103

Технологическая задача.

 

Цель  задачи: Определение кратчайшего  пути передачи продукции между цехами.

 

В данной задаче ершины отражают производственные элементы (цеха), а дуги –

потоки сырья, материалов и продукции между  ними.

 

Как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из одной вершины графа в другую, то есть попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.1).

 

  Рис.1.

 

 

 

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

 

Таблица 1.

 

 

Вопрос: как кратчайшим путем попасть из вершины 1 в вершину 4?

 

Решение. Введем обозначение: С(Т) - длина кратчайшего  пути из вершины 1 в вершину Т. (Поскольку  любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

 

Для исходных данных, представленных на рис.1 и в табл.1, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1. Кроме того, очевидно, что С(1) = 0.

 

В вершину 4 можно  попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

 

С(4) = min {С(2) + 4; С(5) + 5}.

 

Таким образом, проведена реструктуризация (упрощение) задачи - нахождение С(4) сведено к  нахождению С(2) и С(5).

 

 В вершину  5 можно попасть либо из вершины  3, пройдя путь, равный 2, либо из  вершины 6, пройдя путь, равный 3. Поэтому  справедливо соотношение

 

С(5) = min {С(3) + 2; С(6) + 3}.

 

Мы знаем, что  С(3) = 1. Поэтому

 

С(5) = min {3; С(6) + 3}.

 

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

 

В вершину 2 можно  попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

 

С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

 

Нам известно, что  С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

 

С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

 

Теперь мы можем  найти С(4):

 

С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

 

Таким образом, длина кратчайшего  пути равна 8. Из последнего соотношения  ясно, что в вершину 4 надо идти через  вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно  попасть только из вершины 1. Итак, кратчайший путь таков:

 

1 → 3 → 5 → 4 .

 

Задача о кратчайшем пути для конкретных исходных данных (рис.1 и табл.1) полностью решена.