Задача о кратчайшим пути между двумя вершинами ориентированного графа и ее экономическая интерпретация.
Постановка задачи
Постановка задачи состоит в следующем. Задан конечный ориентированный граф G(x,гx), или G(x,u). Каждой дуге графа “u” поставлено в соответствие некоторое число l(u)³0, называемое длинной дуги “u”. Длинной пути m называется сумма длин дуг, составляющих данный путь.
.
Требуется для двух фиксированных вершин xo и xn графа G(x,u) найти самый короткий соединяющий их путь.
К данной задаче может быть сведена следующая задача экономического содержания. Задана сеть дорог соединяющих пункты xi (i=0,1,…,n). Найти путь, соединяющий пункты xo и xn, по которому можно доставить груз в кратчайшее время. При этом время доставки груза из пункта xi в xj (i,jÎ0,…,n) задано и равно l(uij)=l(xi,xj)³0.
Если под длинной дуги l(xi,xj) понимать стоимость перевозки груза из пункта xi в xj, то содержание задачи составит определение такого пути из пункта xi в xj, на котором затраты на транспортировку были бы минимальными.
Пример.
Имеем 6 пунктов Х (X0,…,X6). Сеть дорог, связывающих эти пункты, изображена на графе (рис.3.3.1).
Время доставки груза из i-го пункта в j-й, т.е. l(xi,xj), задано и изображено числом в кружке, записанным рядом с дугой (xi,xj). Так, l(x0,x1)=2, l(x0,x2)=4, l(x0,x3)=5, l(x1,x4)=3 и т.д.
Рис. .1.
Требуется определить путь, по которому из пункта x0 в пункт x5 можно доставить груз в кратчайшие время, и само кратчайшее время доставки.
Итак, задача о кратчайшем пути между двумя фиксированными вершинами ориентированного графа предполагает, во-первых, определение длины кратчайшего пути, во-вторых, определение самого кратчайшего пути.
Алгоритм.
Алгоритм решения этой задачи позволяют определить кратчайший путь и его длину за конечное число шагов. Каждая вершина графа получает некоторую числовую метку на первом шаге. Затем метки, вообще говоря, могут меняться, становясь на некотором шаге постоянным числом. Установившаяся метка данной вершины есть кратчайшее расстояние от этой вершины до вершины x0. Если пути, соединяющего x0 и xn, не существует, будем считать длину кратчайшего пути между этими вершинами равной + 
.
Алгоритм состоит в последовательном выполнении следующих операций:
1. На первом шаге ставим следующие метки: для вершины x0 l0=0, для любой другой вершины xi lj=+ (i=1,…,n);
2. Ищем на графе такую дугу (xi,xj), для которой lj-li>l(xi,xj). Причем разность - считаем равной 0. Если такая дуга найдется, меняем метку вершины xj на 
. Если такой дуги не найдется, то пути, соединяющего x0 с xn, не существует, т.к. из x0 ни в какую другую вершину графа не идет ни одна дуга.;
3. Повторяем процедуру пункта 2 до тех пор, пока метки вершин не перестанут меняться.
Установившиеся метки обозначим l*i (I=1,2,…,n). При этом может быть два случая:
1) l*n=+ .
Это значит, что пути, соединяющего x0 и xn, не существует. Длина кратчайшего пути равно + .
2) l*n – конечное число.
Оно равно кратчайшему расстоянию между вершинами x0 и xn.
Кратчайший путь получаем следующим образом. Ищем вершину xp1 такую, что 
, затем xp2, для которой 
и т.д. до тех пор, пока не придем в вершину xp(k+1)=x0. Путь, проходящий через отмеченные вершины 
, является кратчайшим.
Как следует из построения и правил изменения меток, метки вершины xi (i=1,…,n) могут меняться конечное число раз (метка вершин x0 l0=0 не меняется), т.к. конечная метка всякой вершины равна длине некоторого пути из x0 в данную вершину xi.
Из построения следует, что отмеченный путь m ( ) – есть кратчайший путь. В самом деле, пусть существует другой путь 
из вершины x0 в xn, проходящий через вершины x0,x1,x2,…,xr,xn. Из построения следует, что
Складывая эти неравенства и учитывая, что lx*0=0, получим 
, т.е. 
. Заметим, что решение задачи может не быть однозначным, т.е. существует несколько путей минимальной длины из вершины x0 в xn.
Рассмотренный алгоритм известен в литературе как алгоритм Форда.
Решение данной задачи можно ускорить, сократив число шагов, если пользоваться формулой
. (1)
Задача об отыскании кратчайшего пути между двумя вершинами ориентированного графа может быть решена методами целочисленного программирования. Решение по приведенному алгоритму является более простым.
Обратимся к приведенному выше примеру. Определим кратчайший путь, соединяющий пункты x0 и x5. При этом будем пользоваться формулой (3.3.1)
Для вершины x0 полагаем l0=0. Для всех остальных вершин li=+ (i=1…,5). Затем ищем дугу, для которой lj-l0>l(x0,xj). Начнем с вершины x1.
l1-l0= >l(x0,x1)=2.
Следовательно меняем метку вершины x1 на
l’1=l0+l(xo,x1)=2
Аналогично определяем метку вершины X2
l’2=l0+l(xo,x1)=2
Чтобы найти изменившуюся метку вершины X3, следует воспользоваться формулой (6.1), т.к. в вершину X3 направлены две дуги, идущие из двух разных верши x0 и x1:
| l’3=min{[l’1+l(x1,x3)],[ l0+l(x0,x3)]}=min{(2+4),(0+5)}=5 | (xo) |
Аналогично определяем новые метки для вершин x4x5:
| l’4=min{[l’1+l(x1,x4)],[ l’3+l(x3,x4)]}=min{(2+3),(5+6)}=5 | (x1) |
| l’5=min{[l’2+l(x2,x5)],[l’3+l(x3,x5)],[l’4+l(x4,x5)]}= =min{(4+7),(5+4),(5+2)}=7 | (x4) |
В данном случае получили установившиеся метки вершин на втором шаге (на первом шаге полагая l0=0, li=+ ). Каждая из меток l’i – длина кратчайшего пути из вершин x0 в данную вершину xj. Длина кратчайшего пути из x0 в x5 есть
l*5=l’5=7.
При подсчете значений l’j справа в скобках отмечены вершины, по которым достигается минимум. Так, для x5 l’5=7, если прийти в эту вершину из вершины x4, т.е. l’5=l’4+l(x4,x5). Метка для вершины x5 примет большее значение, если прийти в x5 из x2 или x3. Следовательно, кратчайший путь в x5 проходит через вершину x4 (P1=4 в приведенных выше обозначениях). В x4 он идет через вершину x1 (P2=1), в x1 из x0 (P3=P4=0). Итак, кратчайший путь из вершины x0 в x5 проходит через вершины x0,x1,x4,x5. Искомый путь m есть (x0,x1,x4,x5); l(m)=7.
В рассмотренном примере установившиеся метки получили за один шаг, потому что, воспользовавшись формулой (3.3.1), определили кратчайший путь между входом и выходом графа-сети. Заметим, что для графов-сетей кратчайший путь между входом и выходом графов всегда существует. Причем он может быть получен за один шаг без предварительного изменения меток, т.е. алгоритм становится совсем простым, если пользоваться формулой (3.3.1) и правильной нумераций вершин графа, что и было проделано в этой задаче.
Дата добавления: 2016-01-26; просмотров: 1655;