Создан заказ №3314327
8 ноября 2018
ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ Задана сеть представленная на рис 4 1 Требуется определить кратчайшие маршруты сети
Как заказчик описал требования к работе:
Выполнить задания из файлов во вложении (4, 5 и 6.docx). Там, где есть вариант - выбрать ПЕРВЫЙ. Для выполнения последнего задания к заказу приложены лекции, в которых можно найти необходимую информацию (лекции.zip).
Фрагмент выполненной работы:
ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ
Задана сеть, представленная на рис. 4.1. Требуется определить кратчайшие маршруты сети, записанные в матрицах C и D
Использовать вычислительный алгоритм определения кратчайших маршрутов лекций 9 - 10 .
,
Рис.4.1 Конфигурация заданной сети
S=
Рис .4.2 Матрица S конфигурации
Решение:
Для решения задачи воспользуемся алгоритмом Дейкстры. Блок-схема алгоритма приведена на рис.4.3.
Рис.4.3. (работа была выполнена специалистами author24.ru) Алгоритм определения кратчайших путей
Сформируем исходные матрицы на шаге 0 алгоритма. Здесь S – матрица конфигурации; C – матрица весов путей; D – матрица маршрутов.
Далее приведен порядок выполнения алгоритма и промежуточные результаты.
0.
S=
1 1 1 0 0
1 1 0 1 0
1 0 1 1 1
0 1 1 1 0
0 0 1 0 1
C=
0 10 11 ∞ ∞
10 0 ∞ 12 ∞
11 ∞ 0 13 14
∞ 12 13 0 ∞
∞ ∞ 14 ∞ 0
D=
1 2 3
1 2
4
1
3 4 5
2 3 4
3
5
I=1; j=1. I=j; j\=5.
I=1; j=2. i\=j k=1; k=I; k\=5;
I=1; j=2; k=2. k\=I; k=j; k\=5;
I=1; j=2; k=3. k\=I; k\=j; c3(1,2)=c(1,3)+c(3,2)=11+∞=∞\<c(1,2)=10; k\=5
I=1; j=2; k=4. k\=I; k\=j; c4(1,2)=c(1,4)+c(4,2)= ∞+12=∞\<c(1,2)=10
I=1;j=2; k=5. k\=I; k\=j; c5(1,2)=c(1,5)+c(5,2)= ∞+∞=∞\<c(1,2);k=5; j\=5
I=1; j=3; i\=j/ k=1; k=I; k\=5
I=1; j=3; k=2. k\=I; k\=j; c2(1,3)=c(1,2)+c(2,3)=10+∞=∞\<c(1,3)=11;k\=5
I=1; j=3; k=3. k\=I; k=j;k\=5
I=1; j=3; k=4. k\=I; k\=j. c4(1,3)=c(1,4)+c(4,3)= ∞+13=∞\<c(1,3)=11; k\=5
I=1; j=3; k=5. k\=I; k\=j. c5(1,3)=c(1,5)+c(5,3)= ∞+14=∞\<c(1,)=11; k=5; j\=5
I=1; j=4; k=1.k=I; k\=5
I=1; j=4; k=2. k\=I; k\=j. c2(1,4)=c(1,2)+c(2.4)=10+12=22<c(1,4)= ∞
C(1,4)=22; d(1,4)=2; k\=5
I=1; j=4; k=3. k\=I;k\=j. c3(1,4)=c(1,3)+c(3,4)=11+13=24\<c(1,4)=22; k\=5
I=1; j=4; k=4. k\=I; k=j; k\=5
I=1; j=4; k=5. k\=I; k\=j; c5(1,4)=c(1,5)+c(5,4)= ∞+∞=∞\<c(1,4)=22; k=5; j\=5
I=1; j=5; k=1; k=i
I=1; j=5; k=2. k\=I; k\=j. c2(1,5)=c(1,2)+c(2,5)=10+∞=∞\<c(1,5)= ∞; k\=5
I=1; j=5; k=3; k\=I; k\=j; c3(1,5)=c(1,3)+c(3,5)=11+14=25< c(1,5)= ∞; c(1,5)=25; d(1,5)=3; k\=5
I=1; j=5; k=4;k\=I; k\=j; c4(1,5)=c(1,4)+c(4,5)= ∞+∞=∞\<c(1,5)=25; k\=5
I=1; j=5; k=5. k\=I; k=j; k=5; j=5; i\=5;
Скорректированные матрицы
С=
0 10 11 22 25
10 0 ∞ 12 ∞
11 ∞ 0 13 14
∞ 12 13 0 ∞
∞ ∞ 14 ∞ 0
D=
1 2 3 2 3
1 2 1 4 1
1
3 4 5
2 3 4
3
5
25. I=2; j=3; k=1. k\=I; k\=j; c1(2,3)=c(2,1)+c(1,3)=10+11=21<c(2,3)= ∞; c(2,3)=21; d(2,3)=1; k\=5;
I=2; j=3; k=2. K=I; k\=5
I=2; j=3; k=3. k\=I; k=j; k\=5
I=2; j=3; k=4. k\=I; k\=j; c4(2,3)=c(2,4)+c(4,3)=12+13=25\<c(2,3)= 21; k\=5
I=2; j=3; k=5. k\=I; k\=j; c5(2,3)=c(2,5)+c(5,3)= ∞+14=∞\<c(2,3)=21; k=5; j\=5
I=2; j=4; k=1. k\=I; k\=j; c1(2,4)=c(2,1)+c(1,4)=10+22=32\<c(2,4)=12; k\=5
I=2; j=4; k=2. K=I; k\=5
I=2; j=4; k=3. k\=I; k\=j; c3(2,4)=c(2,3)+c(3,4)= ∞+13=∞\<c(2,4)=12; k\=5
I=2; j=4; k=4. k\=I; k=j; k\=5
I=2; j=4; k=5. k\=I; k\=j; c5(2,4)=c(2,5)+c(5,3)= ∞+14=∞\<c(2,4)=12; k=5
I=2; j=5; k=1; k\=I; k\=j; c1(2,5)=c(2,1)+c(1,5)=10+25=35<c(2,5)= ∞; c(2,5)=35; d(2,5)=1; k\=5
I=2; j=5; k=2. K=I; k\=5
I=2; j=5; k=3...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
9 ноября 2018
Заказ завершен, заказчик получил финальный файл с работой
5
ОПРЕДЕЛЕНИЕ КРАТЧАЙШИХ МАРШРУТОВ
Задана сеть представленная на рис 4 1 Требуется определить кратчайшие маршруты сети.jpg
2018-11-12 21:59
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Всем советую этого автора! Всё в срок, ответственный подход к работе, выполнено с подробными объяснениями) всё очень круто) спасибо огромное автору)
Хочешь такую же работу?
300 ₽
