Элементы теории графов. Экономические приложения

курсовая работа

Задача о кратчайшем пути

Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины - вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг

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

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

Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной. Легко показать, что в сети без контуров всегда существует правильная нумерация.

Обозначим - длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Алгоритм 1.

Шаг 0: Помечаем нулевую вершину индексом ;

Шаг k: помечаем вершину k индексом i<k;

Индекс выхода будет равен длине кратчайшего пути. (Алгоритм 1 для задач динамического программирования отражает принцип оптимальности Беллмана: если ищется кратчайший путь между двумя точками, то длина пути между любыми двумя точками кратчайшего пути также должна быть минимальна.) На рисунке 2 приведен пример применения алгоритма 1 для определения кратчайшего пути (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).

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

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

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевую вершину индексом , все остальные вершины индексами , i = 1, n;

Шаг k: Рассматриваем все дуги. Если для дуги (i; j) >, то вычисляем новое значение ;

Индексы устанавливаются за конечное число шагов. Обозначим - установившиеся значения индексов, которые обладают следующим свойством: величина равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.

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

Алгоритм 3.

Шаг 0: Помечаем нулевую вершину индексом ;

Шаг k: Пусть уже помечено некоторое множество вершин. Обозначим Q - множество непомеченных вершин, смежных с помеченными. Для каждой вершины вычисляем величину где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина минимальна, индексом .

Подобную процедуру повторяем до тех пор, пока не будет помечена вершина n. Длина кратчайшего пути равна , а сам кратчайший путь определяется так, как это было описано выше.

Аналогично задаче о кратчайшем пути формулируется и решается задача о максимальном (длиннейшем) пути - достаточно изменить знаки дуг на противоположные и решить задачу о кратчайшем пути. Для существования решения задачи о максимальном пути необходимо и достаточно отсутствия контуров положительной длины.

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

Пример 1.

Рис. 3. Исходные данные к задаче о кратчайшем пути.

Ситуацию можно описать не только ориентированным графом, но и таблицей (табл. 1).

Табл.1. Исходные данные к задаче о кратчайшем пути

Начало дуги

Конец дуги

Время в пути

1

2

7

1

3

1

2

4

4

2

6

1

3

2

5

3

5

2

3

6

3

5

2

2

5

4

5

6

5

3

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

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

Для исходных данных, представленных на рис. 3 и в табл. 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.

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

Пример 2.

Найти кратчайший путь (длина пути) из Академгородка (остановка Цветной проезд) до железнодорожного вокзала.

Остановки:

1- цветной проезд

2- дом быта

3,3- институт ядерной физики

4_Баня №22

5_Речной вокзал

6 - Сеятель

7 - кафе «Огонек»

8 - Мост

9 - Главный Вокзал

Найти кратчайший путь из вершины 1 в вершины 9.

Исходные данные:

Рис. 4

Табл. 2

Начало дуги

Конец дуги

Длина пути (км.)

1

2

3

1

3

1,7

1

3

3,06

1

4

10,9

1

5

26,78

2

6

0,5

3

7

7,6

3

7

7,6

4

8

21,57

5

8

4,26

5

9

4,35

6

9

25

7

5

19

8

9

2,55

Решение: С (Т) - длина кратчайшего пути из вершины 1 в вершину Т. Нам необходимо найти С(9).

С(1)=0, С(2)=3 (в вершину 2 входит только одна стрелка, ее длина равна 3).

В вершину 9 можно попасть из вершины 5, пройдя путь 4,35, из вершины 6, пройдя путь 25 и из вершины 8, пройдя путь 2,55.

Следовательно, С(9) = min {С(5) + 4,35; С(6) + 25; С(8) + 2,55}

Таким образом необходимо найти С(5), С(6), С(8).

В вершину 5 можно попасть из вершины 1, пройдя путь 26,78, либо из вершины 7, пройдя путь 19

С(5) = min {С(1) + 26,78; С(7) + 19}

Необходимо найти С(7). В вершину 7 можно попасть из вершины 3, пройдя путь 7,6 и из 3 пройдя 7,6.

С(7) = min {С(3) + 7,6; С(3) + 7,6}= min {1,7+7,6; 3,06+7,6}=9,3

С(5) = min {26,78; 9,3+ 19}=26,78

В вершину 6 можно попасть из вершины 2, пройдя путь равный 0,5

С(6)=С(2)+0,5=3+0,5=3,5

В вершину 8 можно попасть из вершины 4, пройдя путь 21,57 и из вершины 5, пройдя путь 4,62.

С(8) = min {С(4) + 21,57; С(5) + 4,26}

С(4)=10,9 (из условия).

С(8) = min {10,09+ 21,57; 26,78 + 4,26}=31,4

Следовательно

С(9)= min {26,78+4,35; 3,5+25; 31,4+2,55}= min {31,13; 28,5; 33,95}=28,5

Таким образом, длина кратчайшего пути равна 28,5 км.

Кратчайший путь: 1 > 2 > 6 > 9.

Делись добром ;)