Построение кратчайших и максимальных путей
в ориентированной сети
Вариант № 1
Цель работы 1:
Научиться применять алгоритмы нахождения кратчайших и наиболее длинных путей в графах.
Задание.
Нарисовать диаграммы ориентированных сетей G1X1,A1, G2X2,A2, заданных весовыми матрицами W1 и W2. Построить для сети G1 кратчайший путь от узла x1 до узла x6 с помощью алгоритма Дейкстры и максимальный путь.
W1=-∞∞∞∞∞ 7-∞∞∞∞ 810-∞∞∞ 1152-∞∞ ∞834-∞ ∞∞2∞6-, W2=-∞∞∞∞∞ 15-∞∞∞∞ ∞4-10∞∞ 12-6∞-∞∞ ∞2-47-∞ ∞∞2∞-5-.
Решение
Нахождение кратчайшего пути с помощью алгоритма Дейкстры.
Рассмотрим сеть G1X1,A1, состоящую из шести узлов и найдем кратчайший путь из узла x1 в узел x6 (рис. 1).
Рис. 1. Сеть G1X1,A1
На рисунке изображена сеть G1X1,A1. Узлы ее представлены в виде кружков, в которые будем вписывать получаемые в результате работы алгоритма метки.
Этап 1. (нахождение длины кратчайшего пути)
Шаг 0. dx1=0*, dx2=dx3=dx4=dx5=dx6=∞, u=x1 – текущий узел.
Рис. 2. Узел x1 получил постоянную метку
1-я итерация
Шаг 1. Г+u=x2,x3,x4 – узлы, непосредственно следующие за u, для них определяем новые метки:
dx2=mindoldx2,du+wu,x2=min∞,0+7=7
dx3=mindoldx3,du+wu,x3=min∞,0+8=8
dx4=mindoldx4,du+wu,x4=min∞,0+11=11.
Шаг 2. Превращаем метки в постоянную:
mindx2,dx3,dx4,dx5,dx6=min7, 8, 11,∞,∞=7*=dx2.
Шаг 3. x2≠x6, этап 1 не закончен, u=x2 рис. 3.
Рис. 3. Узел x2 получил постоянную метку
2-я итерация
Шаг 1. Г+u=x3,x4, x5 – узлы, непосредственно следующие за x2, для них определяем новые метки:
dx3=mindoldx3,du+wu,x3=min8, 7+10=8
dx4=mindoldx4,du+wu,x4=min11, 7+5=11
dx5=mindoldx5,du+wu,x5=min∞,7+8=15.
Шаг 2
. Превращаем метки в постоянную:
mindx3,dx4,dx5,dx6=min{8, 11, 15, ∞}=8*=dx3.
Шаг 3. x3≠x6, этап 1 не закончен, u=x3 рис. 4.
Рис. 4. Узел x3 получил постоянную метку
3-я итерация
Шаг 1. Г+u=x4,x5,x6 – узел, непосредственно следующий за x3, для него определяем новую метку:
dx4=mindoldx4,du+wu,x4=min11, 8+2=10
dx5=mindoldx5,du+wu,x5=min15, 8+3=11
dx6=mindoldx6,du+wu,x6=min∞, 8+2=10.
Шаг 2. Превращаем метки в постоянную:
mindx4,dx5,dx6=min10, 11, 10=10*=dx4.
Шаг 3. x4≠x6, этап 1 не закончен, u=x4 рис. 5.
Рис. 5. Узел x4 получил постоянную метку
4-я итерация
Шаг 1. Г+u=x5 – узел, непосредственно следующий за x4, для него определяем новую метку:
dx5=mindoldx5,du+wu,x5=min11, 10+4=11.
Шаг 2. Превращаем метки в постоянную:
mindx5,dx6=min11, 10=10*=dx6.
Шаг 3. x6=x6, длина кратчайшего пути из x1 в x6 равна 10 (рис. 6).
Рис. 6. Длина кратчайшего пути до узла x6 равна 10
Таким образом,
dx1=0, dx2=7, dx3=8, dx4=10, dx5=11, dx6=10.
Этап 2. (нахождение кратчайшего пути методом последовательного возвращения).
1-я итерация.
Шаг 1. u=x6, Г_u=x3, x5 – узлы, непосредственно предшествующие u
Заказать работу
на новый заказ в Автор24.
