Построение кратчайших и максимальных путей в ориентированной сети

Расчетно-графическая работа № 1

Построение кратчайших и максимальных путей в ориентированной сети

(Вариант 2)

Цель работы: Научится применять алгоритмы нахождения кратчайших и наиболее длинных путей в графах.

Задание:

Изобразить в виде рисунков ориентированные сети [pic 1], [pic 2],  заданные весовыми матрицами [pic 3] и [pic 4]. Построить для сети[pic 5] кратчайший путь от узла [pic 6]до[pic 7]с помощью алгоритма Дейкстры и максимальный путь. Построить для сети [pic 8]кратчайший путь от узла [pic 9]до[pic 10]с помощью алгоритма Беллмана-Форда.

Весовые матрицы:

Решение

а) Поиск кратчайшего пути от узла X1 до узла X6 для сети G1.Изображаем эту ориентированную сеть в виде графа. Узлы сети будут представлены в виде кружков, в которые будем вписывать получаемые результаты алгоритма метки.

[pic 12][pic 13]

Рис.1.1. Дерево путей

Так как в заданной сети веса неотрицательны,то для нахождения кратчайшего пути от узла X1 до узла X6 воспользуемся алгоритмом Дейкстры (алгоритм расстановки меток), состоящий из 2 этапов.

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

Шаг 1. Присвоение начальных значений.

Полагаем для начального узла d(X1)=0* и считаем эту метку постоянной. Для остальных узлов полагаем d(X2)=d(X3)=d(X4)=d(X5)=d(X6)=∞ и считаем эти метки временными.

Обозначаем текущий узел как U=X1.

Результат приведен на рисунке:

[pic 14]

Рис.1.2. Узел X1 получил постоянную метку

1-ая итерация

Шаг 2. Изменение меток.

По строке матрицы W1 для текущей вершины u=X1находим смежные вершины (вершины, непосредственно следующие за вершиной u):S(u)=.[pic 15]

Для найденных смежных вершин определяем новую метку:

d(X2)=min {dold(X2),d(u)+(u,X2)}=min{∞,0+6}=6

d(X4)=min {dold(X4),d(u)+(u,X4)}=min{∞,0+9}=9

d(X5)=min {dold(X5),d(u)+(u,X5)}=min{∞,0+10}=10

Шаг 3. Превращение метки в постоянную.

Из всех вершин с временными метками выбираем вершину с наименьшим значением метки:

min{d(X2),d(X3),d(X4),d(X5),d(X6)}=min{6,∞,9,10,∞}=6*

Превращение метки в постояннуюd(X2)=6*.

Шаг4. Проверка на завершение этапа 1.

Так как найденная на предыдущем этапе вершина не совпала с конечной вершиной:X2≠X6, то этап 1 не закончен и необходимо выполнить следующую итерацию с шага 2, приняв u=X2.

Результат на рисунке: 

[pic 16]

Рис.1.3. Узел X2 получил постоянную метку

2-ая итерация

Шаг2. Изменение меток.

По строке матрицы W1 для текущей вершины u=X2находим смежные вершины (вершины, непосредственно следующие за вершиной u):S(u)={X3}.

Для найденных смежных вершин определяем новую метку:

d(X3)=min {dold(X3),d(u)+w(u,X3)}=min{∞,6*+7}=13

Шаг 3.Превращение метки в постоянную.

Из всех вершин с временными метками выбираем вершину с наименьшим значением метки:

min{d(X3)}=13

Превращение метки в постояннуюd(X3)=13*.