Міністрерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра математичних
методів в інженерії
ЗВІТ
до лабораторної роботи №9
з курсу «Сучасні методи розв’язку дискретного програмування»
Найкоротший шлях між вершинами орграфа.
Виконав:
ст. гр.
Перевірила:
Крива Н.Р.
Тернопіль 201_
Тема:
Найкоротший шлях між вершинами орграфа.
Мета:
Знайти найкоротший шлях між вершинами оргграфа.
Текст програми:
%Лабораторна робота №9
%
%Варіант
clear all %очистити память
C=[0 3 7 4 6 4;4 0 3 7 8 5;6 9 0 3 2 1;8 6 3 0 9 8;3 7 4 6 0 4;4 5 8 7 2 0];
disp('Відстань між містами:')
fprintf(' %2.0f',1:size(C,2))
fprintf('\n')
for k1=1:size(C,1),
fprintf('%2.0f',k1)
fprintf('%7.2f',C(k1,:))
fprintf('\n')
end
[pTS,fmin]=grTravSale(C);
disp('Порядок обходу міст');
fprintf('%d ',pTS)
fprintf('\nДовжина мінімального шляху =%3.0f\n',fmin)
Відстань між містами:
1 2 3 4 5 6
1 0.00 3.00 7.00 4.00 6.00 4.00
2 4.00 0.00 3.00 7.00 8.00 5.00
3 6.00 9.00 0.00 3.00 2.00 1.00
4 8.00 6.00 3.00 0.00 9.00 8.00
5 3.00 7.00 4.00 6.00 0.00 4.00
6 4.00 5.00 8.00 7.00 2.00 0.00
Порядок обходу міст
1 4 2 3 6 5 1
Довжина мінімального шляху = 19
Висновок:
На даній лабораторній роботі я використав функцію grTravSale для визначення найкоротшого шляху між вершинами орграфа.