Міністрерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра математичних
методів в інженерії
ЗВІТ
до лабораторної роботи №6
з курсу «Сучасні методи розв’язку дискретного програмування»
Знаходження найкоротшого шляху
Виконав:
ст. гр.
Перевірила:
Крива Н.Р.
Тернопіль 201_
Тема:
Знаходження найкоротшого шляху.
Мета:
Потрібно знайти найкоротші шляхи між кожною парою вершин орграфа.
Текст програми:
%Лабораторна робота №6
%
%Варіант
clear all %очистити память
V=[1 2; 1 1; 2 2; 2 1; 3 2; 3 1; 4 2; 4 1];
E=[1 2 1; 1 3 2; 1 4 3; 2 4 4; 4 3 5; 3 5 6; 3 6 7; 4 6 8; 5 6 9; 6 8 10; 5 7 11; 5 8 12; 7 8 13];
s=1;
t=8;
fprintf('Початок шляху s=%d\nКінець шляху t=%d\n',s,t)
grPlot(V(:,1:2),E,'d','','%d'); % малюємо граф
set(get(gcf,'CurrentAxes'),...
'FontName','Times New Roman Cyr','FontSize',12) % встановили шрифт
title('\bfВихідний орграф з зваженими дугами');
[dSP,sp]=grShortPath(E,s,t);
disp('Найкоротший маршрут між всіма вершинами:');
fprintf('%2.0f',1:size(dSP,2));
fprintf('\n');
for k1=1:size(dSP,1),
fprintf('%2.0f',k1)
fprintf('%6.2f',dSP(k1,:))
fprintf('\n')
end
grPlot(V(:,1:2),[sp(1:end-1);sp(2:end)]','d','%d','');
set(get(gcf,'CurrentAxes'),...
'FontName','Times New Roman Cyr','FontSize',12) % встановили шрифт
title(['\bfНайкоротший шлях із вершини'...
num2str(s) ' в вершину ' num2str(s)]);
Початок шляху s=1
Кінець шляху t=8
Найкоротший маршрут між всіма вершинами:
1 2 3 4 5 6 7 8
1 Inf 1.00 2.00 3.00 8.00 9.00 19.00 19.00
2 Inf Inf 9.00 4.00 15.00 12.00 26.00 22.00
3 Inf Inf Inf Inf 6.00 7.00 17.00 17.00
4 Inf Inf 5.00 Inf 11.00 8.00 22.00 18.00
5 Inf Inf Inf Inf Inf 9.00 11.00 12.00
6 Inf Inf Inf Inf Inf Inf Inf 10.00
7 Inf Inf Inf Inf Inf Inf Inf 13.00
8 Inf Inf Inf Inf Inf Inf Inf Inf
Рисунок 1 – Вихідний орграф
Рисунок 2 – Найкоротший шлях
Висновок:
На даній лабораторній роботі я навчився знаходити найкоротший шлях орграфа.