Лабораторная работа
Нахождение минимальных и максимальных путей на орграфах
Вариант 10
Выполнила:
студентка 31 группы
факультета информатики
Перменева М. С.
Проверила:
Титова Г.М.
Омск 2012
Задание 1. По заданной матрице весов Ω графа G найти величину минимального пути и сам путь от вершины s=x1 до вершины t=x7 по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами.
Нахождение величины минимального пути
Этап 1. Нахождение длины кратчайшего пути.
Шаг 1. Т.к. d(s)=0*, то полагаем, d(x1)=0*, X=x1, d(x2)=d(x3)=d(x4)=d(x5)=d(x6)= d(x7)=
Шаг 2. Множество вершин, непосредственно следующих за X= х1 с временными метками
S ={х2, х3, x4, х6}. Пересчитаем временные метки этих вершин:
d(x2)=min{ ,0*+7}=7
d(x3)= min{ ,0*+19}=19
d(x4)= min{ ,0*+20}=20
d(x6)= min{ ,0*+15}=15
Шаг 3. min{x2,x3,x4,x5,x6,x7}=min{7,19,20, ,15, }=7*=x2, тогда X=x2
Шаг 4. т.к. х2≠х7, то возвращаемся ко второму шагу.
2-я итерация
Шаг 2. S ={x4, х5}. Пересчитаем временные метки этих вершин:
d(x4)= min{20,7*+11}=18
d(x5)= min{ ,7*+6}=13
Шаг 3. min{x3,x4,x5,x6,x7}=min{19,18,13,15, }=13*=x5, тогда X=x5
|
|
Шаг 4. т.к. х5≠х7, то возвращаемся ко второму шагу.
3-я итерация
Шаг 2. S ={x6, х7}. Пересчитаем временные метки этих вершин:
d(x6)= min{15,13*+5}=15
d(x7)= min{ ,13*+15}=28
Шаг 3. min{x3,x4,x6,x7}=min{19,18,15,28}=15*=x6, тогда X=x6
Шаг 4. т.к. х6≠х7, то возвращаемся ко второму шагу.
4-я итерация
Шаг 2. S ={х7}
d(x7)= min{28,15*+14}=28
Шаг 3. min{x3,x4,x7}=min{19,18,28}=18*=x4, тогда X=x4
Шаг 4. т.к. х4≠х7, то возвращаемся ко второму шагу.
5-я итерация
Шаг 2. S ={x7}
d(x7)= min{28,18*+13}=28
Шаг 3. min{x3,x7}=min{19,28}=19*=x3, тогда X=x3
Шаг 4. т.к. х3≠х7, то возвращаемся ко второму шагу.
6-я итерация
Шаг 2. S ={x7}
d(x7)= min{28,19*+16}=28
Шаг 3. min{x7}=min{28}=28*=x7, тогда X=x7
Шаг 4. т.к. х7=t=х7, конец первого этапа.