![]()
|
|||||||
Тема 14 задача 1Тема 14 задача 1 Нахождение кратчайшего пути в графе.
Пусть дан граф, дугам которого приписаны веса. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины, при условии, что такой путь существует. Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый). Данная задача может быть разбита на две: 1. Для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим; 2. Найти кратчайшие пути между всеми парами вершин.
Рассмотрим алгоритм решения для задачи: Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi). 1. I(s) = 0, I(Xi) равно бесконечности для всех Хi не равных s и считать эти пометки временными. Положить р = s. 2. Для всех Хi, пренадлежащих Г(р) и пометки которых временны, изменить пометки по следующему правилу: I(Xi) = min[I(Xi), I(p) + c(p, Xi)] 3. Среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)] 4. Считать пометку вешины Хi* постоянной и положить р = Хi*. 5. Если р = t, то I(р) является длинной кратчайшего пути, если нет, перейти к шагу 2. Как только все пометки расставлены, кратчайшие пути получают, используя состношение I(Xi') + c(Xi',Xi) = I(Xi) (1).
Пример решения задачи.
Рассмотрим граф, изображенный на рисунке. Требуется найти все кратчайшие пути от вершины Х1 ко всем остальным вершинам. Матрица весов приведена ниже.
Решение:
I(X1)=0*, I(Xi)=∞, Xi≠X1, p=X1 1) Г{X1}=Г(X1)={X2,X7,X9} I(X2)=min[∞, 0*+10]=10 I(X7)=min[∞, 0*+3]=3 I(X8)=min[∞, 0*+6]=6 I(X9)=min[∞, 0*+12]=12 min[I(X2), I(X3), I(X4), I(X5), I(X6), I(X7), I(X8), I(X9)]=3 X7:I(X7)=3*, p=3 2) Г{X7}=Г(X7)={X2,X4,X6,X9} I(X2)=min[10, 3*+2]=5 I(X4)=min[∞, 3*+4]=7 I(X6)=min[∞, 3*+14]=17 I(X9)=min[12, 3*+24]=12 min[I(X2),I(X3),I(X4),I(X5),I(X6),I(X8),I(X9)]=5 X2:I(X2)=5*, p=5 3) Г{X2}=Г(X2)={X3,X9} I(X3)=min[∞, 5*+18]=23 I(X9)=min[∞, 5*+13]=12 min[I(X3),I(X4),I(X5),I(X6),I(X8),I(X9)]=6 X8:I(X8)=6*, p=6 4) Г{X8}=Г(X8)=[X5,X6,X9] I(X5)=min[∞, 6*+23]=29 I(X6)=min[17, 6*+15]=17 I(X9)=min[12,6*+5]=11 min[I(X3),I(X4),I(X5),I(X6),I(X9)]=7 X4:I(X4)=7*, p=7 5) Г{X4}=Г(X4)={X3,X5,X6} I(X3)=min[23, 7*+25]=23 I(X5)=min[29, 7*+5]=12 I(X6)=min[17, 7*+16]=17 min[I(X3),I(X5),I(X6),I(X9)]=11 X9:I(X9)=11*, p=11 6) Г{X9}=Г(X9)={X6} I(X6)=min[17, 11*+9]=17 min[I(X3),I(X5),I(X6)]=12 X5:I(X5)=12*, p=12 7) Г{X5}=Г(X5)={X6} I(X6)=min[17, 12*10]=17 min[I(X3),I(X6)]=17 X6:I(X6)=17*, p=17 8) Г{X6}=Г(X6)={X3} I(X3)=min[23, 17*+20]=23 X3:I(X3)=23*, p=23
Все вершины имеют пометки.
Найдём кратчайший путь, например, (Х1,Х2). Вершина Х2 имеет пометку 5*. Полагая в соотношении (1) Хi = Х2, получаем I(X2')+с(Х2', Х2) = I(X2) = 5. Единственной такой вершиной является Х7. Далее применяем ещё раз соотношение (1) и получаем путь (Х1,Х7,Х2) и т. д.
|
|||||||
|