Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

СМРЗДП / LAB / lab_6

.doc
Скачиваний:
6
Добавлен:
05.03.2016
Размер:
62.46 Кб
Скачать

Міністрерство освіти і науки України

Тернопільський національний технічний університет

імені Івана Пулюя

Кафедра математичних

методів в інженерії

ЗВІТ

до лабораторної роботи №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 – Найкоротший шлях

Висновок:

На даній лабораторній роботі я навчився знаходити найкоротший шлях орграфа.

Соседние файлы в папке LAB