Этап 1. Нахождение длины кратчайшего пути

Лабораторная работа

Нахождение минимальных и максимальных путей на орграфах

Вариант 10

Выполнила:

студентка 31 группы

факультета информатики

Перменева М. С.

Проверила:

Титова Г.М.

Омск 2012

Задание 1. По заданной матрице весов Ω графа G найти величину минимального пути и сам путь от вершины s=x₁ до вершины t=x₇ по алгоритму Дейкстры, а затем величину максимального пути и сам путь между теми же вершинами.

Нахождение величины минимального пути

Этап 1. Нахождение длины кратчайшего пути.

Шаг 1. Т.к. d(s)=0*, то полагаем, d(x₁)=0*, X=x₁, d(x₂)=d(x₃)=d(x₄)=d(x₅)=d(x₆)= d(x₇)=

Шаг 2. Множество вершин, непосредственно следующих за X= х₁ с временными метками

S ={х₂, х₃, x₄, х₆}. Пересчитаем временные метки этих вершин:

d(x₂)=min{ ,0*+7}=7

d(x₃)= min{ ,0*+19}=19

d(x₄)= min{ ,0*+20}=20

d(x₆)= min{ ,0*+15}=15

Шаг 3. min{x₂,x₃,x₄,x₅,x₆,x₇}=min{7,19,20, ,15, }=7*=x₂, тогда X=x₂

Шаг 4. т.к. х₂≠х₇, то возвращаемся ко второму шагу.

2-я итерация

Шаг 2. S ={x₄, х₅}. Пересчитаем временные метки этих вершин:

d(x₄)= min{20,7*+11}=18

d(x₅)= min{ ,7*+6}=13

Шаг 3. min{x₃,x₄,x₅,x₆,x₇}=min{19,18,13,15, }=13*=x₅, тогда X=x₅

Шаг 4. т.к. х₅≠х₇, то возвращаемся ко второму шагу.

3-я итерация

Шаг 2. S ={x₆, х₇}. Пересчитаем временные метки этих вершин:

d(x₆)= min{15,13*+5}=15

d(x₇)= min{ ,13*+15}=28

Шаг 3. min{x₃,x₄,x₆,x₇}=min{19,18,15,28}=15*=x₆, тогда X=x₆

Шаг 4. т.к. х₆≠х₇, то возвращаемся ко второму шагу.

4-я итерация

Шаг 2. S ={х₇}

d(x₇)= min{28,15*+14}=28

Шаг 3. min{x₃,x₄,x₇}=min{19,18,28}=18*=x₄, тогда X=x₄

Шаг 4. т.к. х₄≠х₇, то возвращаемся ко второму шагу.

5-я итерация

Шаг 2. S ={x₇}

d(x₇)= min{28,18*+13}=28

Шаг 3. min{x₃,x₇}=min{19,28}=19*=x₃, тогда X=x₃

Шаг 4. т.к. х₃≠х₇, то возвращаемся ко второму шагу.

6-я итерация

Шаг 2. S ={x₇}

d(x₇)= min{28,19*+16}=28

Шаг 3. min{x₇}=min{28}=28*=x₇, тогда X=x₇

Шаг 4. т.к. х₇=t=х₇, конец первого этапа.