Graf2

Петербургский государственный университет путей сообщения

Императора Александра I

Кафедра «Математика и моделирование»

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

«Построение кратчайших путей в ориентированной сети»

Выполнил студент Баранов Д.А.

Факультет: АИТ

Группа: АР-709

Номер зачётной книжки: 01-709-02

Проверил: Боровских Ю.Б.

Санкт-Петербург

2018

Задание.

Изобразить в виде рисунков ориентированные сети , заданные весовой матрицей . Построить для сети максимальный путь от узла до узла с помощью алгоритма Дейкстры.

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

Полагаем для начального узла p(X1)=0 и считаем эту метку постоянной.

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

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

По строке матрицы W₁ для текущей вершины u=Х₁‚ находим вершины

следующие, непосредственно следующие за вершиной u: Г₊(u)={Х₂}.

p(Хi)=max{p(Хj)+w(Xi;Xj):Xj∈ Г(Хi)}

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

р(Х₂) = max{p(X₁)+w(u;X₂)}=max{0+6}=6

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

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

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

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

По строке матрицы W₁ для текущей вершины u=Х₂‚ находим вершины

следующие, непосредственно следующие за вершиной u: Г+(u)={Х₃}.

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

р(Х₃) = max{p(X₂)+w(u;X₃)}=max{6+7}=13

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

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

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

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

По строке матрицы W₁ для текущей вершины u=Х₃‚ находим вершины

следующие, непосредственно следующие за вершиной u: Г+(u)={Х₄}.

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

р(Х₄) = max{p(X₃)+w(u;X₄)}=max{13+6}=19

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

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

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

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

По строке матрицы W₁ для текущей вершины u=Х₄‚ находим вершины

следующие, непосредственно следующие за вершиной u: Г+(u)={Х₅}.

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

р(Х₅) = max{p(X₄)+w(u;X₅)}=max{19+4}=23

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

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

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

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

По строке матрицы W₁ для текущей вершины u=Х₅‚ находим вершины

следующие, непосредственно следующие за вершиной u: Г+(u)={Х₆}.

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

р(Х₆) = max{p(X₅)+w(u;X₆)}=max{23+8}=31

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

Так как найденная на предыдущем этапе вершина совпала с конечной вершиной: Х₆=Х₆, то этап 1 закончен.

Принимаем u=Х₆.

Таким образом: p(Х1)=0; p(Х2)=6; p(Х3)=13; p(Х4)=19; p(Х5)=23; p(Х6)=31.

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

Построение кратчайшего пути от узла Х1 до узла Х6 для сети G2 с помощью алгоритма Беллмана-Форда.

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

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

Полагаем для начального узла d(Х₁) =0 .Для остальных узлов полагаем d(Х₂)=d(X₃)=d(X₄)=d(X₅)=d(X₆)=∞.

Очередь Q, состоящая из вершин ‚ которые необходимы для анализа возможности уменьшения меток вершин, не находящихся в данный момент в очереди, но достижимые из неё за один шаг , ВЫГЛЯДИТ Q:={x₁}.

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

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

Шаг 2. Корректировка меток в очереди.

l) Обозначаем вершину‚ стоящую в начале очереди как u= Х1. Удаляем из очереди q вершину u:Q:=Q-{u}=Q-{Хl}=ø

2) По строке матрицы W2 для текущей вершины u=Х1 находим вершины, непосредственно следующие за вершиной u: Г+(u)={X2, Х4}.

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

d(Х2)= min {dold (Х2), d(u)+w(u‚Х2)}=min{∞; 0 + 15} = 15

2.1) Так как d(Х2)=5< dold(Х2)=∞‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершины Х2 не было ранее в очереди и

нет в ней на данный момент, то ставим её в конец очереди: Q:={Х2}

d(X4)= min {dold(X4), d(u)+w(u,Х4)}=min{∞; 0 + 12} = 12

2.1) Так как d(Х4)=12< dold(Х4)=∞‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершины Х4 не было ранее в очереди и

нет в ней на данный момент, то ставим её в конец очереди: Q:={Х2,X4}

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

Так как очередь не пуста О=ø‚ то этап 1 не закончен и необходимо выполнить следующую итерацию с шага 2.

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

Шаг 2. Корректировка меток в очереди.

l) Обозначаем вершину‚ стоящую в начале очереди как u=Х2. Удаляем из очереди q вершину u:Q:=Q-{u}=Q-{Х2}={X4}

2) По строке матрицы W2 для текущей вершины u=Х2 находим вершины, непосредственно следующие за вершиной u: Г+(u)={X3, Х4, Х5}.

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

d(Х3)= min {dold (Х3), d(u)+w(u‚Х3)}=min{∞; 15 + 4} = 19

2.1) Так как d(Х3)=19< dold(Х3)=∞‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершины Х3 не было ранее в очереди и её

нет в ней на данный момент, то ставим её в конец очереди: Q:={Х4, Х3}

d(X4)= min {dold(X4), d(u)+w(u,Х4)}=min{12; 15-6} = 9

2.1) Так как d(Х4)=9< dold(Х4)=12‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершина Х4 была ранее в очереди, то ставим её в конец очереди: Q:={Х4, Х3, Х4}

d(X5)= min {dold(X5), d(u)+w(u,Х5)}=min{∞; 15+2} = 17

2.1) Так как d(Х5)=17< dold(Х5)=∞‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершина Х5 была ранее в очереди, то ставим её в конец очереди: Q:={Х4, Х3, Х4, Х5}

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

Так как очередь не пуста О=ø‚ то этап 1 не закончен и необходимо выполнить следующую итерацию с шага 2.

3-ая итерация.

Шаг 2. Корректировка меток в очереди.

l) Обозначаем вершину‚ стоящую в начале очереди как u=Х4. Удаляем из очереди q вершину u:Q:=Q-{u}=Q-{Х4}={X3, Х4, Х5}

2) По строке матрицы W2 для текущей вершины u=Х4 находим вершины, непосредственно следующие за вершиной u: Г+(u)={X3, Х5}.

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

d(Х3)= min {dold (Х3), d(u)+w(u‚Х3)}=min{19; 9+10} = 19

2.1) Так как d(Х3)=19= dold(Х3)=19‚ то пропускаем к подшаг 2.2

d(X5)= min {dold(X5), d(u)+w(u,Х5)}=min{17; 9+7} = 16

2.1) Так как d(Х5)=16< dold(Х5)=17‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершина Х5 была ранее в очереди, то ставим её в конец очереди: Q:={Х3, Х4, Х5, Х5}

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

Так как очередь не пуста О=ø‚ то этап 1 не закончен и необходимо выполнить следующую итерацию с шага 2.

4-ая итерация.

Шаг 2. Корректировка меток в очереди.

l) Обозначаем вершину‚ стоящую в начале очереди как u=Х3. Удаляем из очереди q вершину u:Q:=Q-{u}=Q-{Х3}={X4, Х5, Х5}

2) По строке матрицы W2 для текущей вершины u=Х3 находим вершины, непосредственно следующие за вершиной u: Г+(u)={X5, Х6}.

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

d(Х5)= min {dold (Х5), d(u)+w(u‚Х5)}=min{16; 19-4} = 15

2.1) Так как d(Х3)=15< dold(Х5)=16‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершина Х5 была ранее в очереди, то ставим её в конец очереди: Q:={Х4, Х5, Х5, Х5}

d(X6)= min {dold(X6), d(u)+w(u,Х6)}=min{∞; 19+2} = 21

2.1) Так как d(Х6)=16< dold(Х6)=∞‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершины Х6 не было ранее в очереди и её

нет в ней на данный момент, то ставим её в конец очереди: Q:={Х4, Х5, Х5, Х5, Х6}

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

Так как очередь не пуста О=ø‚ то этап 1 не закончен и необходимо выполнить следующую итерацию с шага 2.

5-ая итерация.

Шаг 2. Корректировка меток в очереди.

l) Обозначаем вершину‚ стоящую в начале очереди как u=Х4. Удаляем из очереди q вершину u:Q:=Q-{u}=Q-{Х4}={X5, Х5, Х5, Х6}

2) По строке матрицы W2 для текущей вершины u=Х4 находим вершины, непосредственно следующие за вершиной u: Г+(u)={X3, Х5}.

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

d(Х3)= min {dold (Х3), d(u)+w(u‚Х3)}=min{19; 9+10} = 19

2.1) Так как d(Х3)=19= dold(Х5)=19‚ то пропускаем к подшаг 2.2

d(X5)= min {dold(X5), d(u)+w(u,Х5)}=min{15; 9+7} = 16

2.1) Так как d(Х5)=16> dold(Х5)=15‚ то пропускаем к подшаг 2.2

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

Так как очередь не пуста О=ø‚ то этап 1 не закончен и необходимо выполнить следующую итерацию с шага 2.

6-ая итерация.

Шаг 2. Корректировка меток в очереди.

l) Обозначаем вершину‚ стоящую в начале очереди как u=Х5. Удаляем из очереди q вершину u:Q:=Q-{u}=Q-{Х5}={Х5, Х5, Х6}

2) По строке матрицы W2 для текущей вершины u=Х5 находим вершины, непосредственно следующие за вершиной u: Г+(u)={Х6}.

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

d(Х6)= min {dold (Х6), d(u)+w(u‚Х6)}=min{21; 15-5} = 10

2.1) Так как d(Х6)=10< dold(Х6)=21‚ то переходим к подшагу 2.2

2.2) Корректировка очереди : так как вершина Х6 была ранее в очереди, то ставим её в конец очереди: Q:={Х6, Х6}

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

Так как очередь пуста О≠ø‚ то этап 1 закончен, переходим к этапу 2.

Итог этапа 1 на рисунке:

Этап 2. Построение кратчайшего пути.

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

Шаг 1. Последовательный поиск дуг кратчайшего пути.

По строке матрицы W2 для текущей вершины u=Х6 находим вершины, предшествующие вершине u: Г-(u)={Х3, Х5}.

Из найденных вершин находим ту, для которой выполняется d(u)=d(Xi)+w(Xi+u):

d(u)=d(X6)=10

для Х3: (Х3)+w(Х3+u)=19+2=21≠d(u)

для Х5: (Х5)+w(Х5+u)=15-5=10=d(u)

Так как выполняется условие d(u)=d(Х5), то вершина Х5 включается в искомый путь.

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

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

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

Шаг 1. Последовательный поиск дуг кратчайшего пути.

По строке матрицы W2 для текущей вершины u=Х5 находим вершины, предшествующие вершине u: Г-(u)={Х2, Х3,Х4}.

Из найденных вершин находим ту, для которой выполняется d(u)=d(Xi)+w(Xi+u):

d(u)=d(X5)=15

для Х2: (Х2)+w(Х2+u)=15+2=17≠d(u)

для Х3: (Х3)+w(Х3+u)=19-4=15=d(u)

для Х4: (Х4)+w(Х4+u)=9+7=16≠d(u)

Так как выполняется условие d(u)=d(Х5), то вершина Х3 включается в искомый путь.

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

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

3-ая итерация.

Шаг 1. Последовательный поиск дуг кратчайшего пути.

По строке матрицы W2 для текущей вершины u=Х3 находим вершины, предшествующие вершине u: Г-(u)={Х2, Х4}.

Из найденных вершин находим ту, для которой выполняется d(u)=d(Xi)+w(Xi+u):

d(u)=d(X3)=19

для Х2: (Х2)+w(Х2+u)=15+4=19=d(u)

для Х4: (Х4)+w(Х4+u)=9+10=19=d(u)

Так как выполняется условие d(u)=d(Х2), то вершина Х2 включается в искомый путь.

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

4-ая итерация.

Шаг 1. Последовательный поиск дуг кратчайшего пути.

По строке матрицы W2 для текущей вершины u=Х2 находим вершины, предшествующие вершине u: Г-(u)={Х1}.

Из найденных вершин находим ту, для которой выполняется d(u)=d(Xi)+w(Xi+u):

d(u)=d(X3)=15

для Х1: (Х1)+w(Х1+u)=0+15=15=d(u)

Так как выполняется условие d(u)=d(Х1), то вершина Х1 включается в искомый путь.

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

Так как найденная на предыдущем этапе вершина совпала с начальной вершиной: Х1=Х1, то этап 2 закончен.

Найденный кратчайший путь M={(Х1,Х2); (Х2,Х3); (Х3,Х5); (Х5,Х6)}

Длина кратчайшего пути d=(Х1,Х6)=10

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