Автор: Пользователь скрыл имя, 12 Марта 2012 в 18:14, курсовая работа
Главной целью курсовой работы является исследование возможностей языка программирования Pascal для нахождения кратчайшего пути между двумя вершинами с заданным количеством ребер, а именно реализации метода Шимбелла.
Из чего следует ряд задач, поставленных на время выполнения курсовой работы:
Изучить источники информации о теории графов.
Рассмотреть возможности метода Шимбелла для нахождения кратчайшего пути в графе.
Воспользоваться возможностями Pascal как языком программирования для реализации метода Шимбелла.
Разработать программу в Pascal ABC, которая находила бы кратчайший путь методом Шимбелла.
Научиться обрабатывать фактический материал, а так же работать с ним для представления его в форме таблиц и блок-схем.
Проанализировать полученные результаты.
Введение……………………………………………………………………....…..3
Глава 1. Теория графов…………………….…………………………….……..5
1.1. Основные понятия теории графов…………………………………..…..5
1.2. Определение кратчайшего пути в графах…………….………………...7
1.3. Метод Шимбелла…………………………………………………………8
1.4. Обзор существующих методов нахождения кратчайших путей…….10
Глава 2. Описание среды программирования……………………………...13
2.1. Pascal как язык программирования…………………………………….13
2.2. Система Pascal ABC ……………………………………………………14
Глава 3. Программа определения кратчайшего пути в графе…………...16
3.1. Реализация метода Шимбелла………………………………………….16
Заключение……………………………………………………………………...21
Библиографический список………………………
end;
matr3[i,k]:=max_mas(mas);
end;
mnozh2:=matr3;
end;
procedure vivod(mas:arr2);
var i,j:char;
begin
for i:='a' to n do begin
write('# ');
for j:='a' to n do begin
write(mas[i,j]:3,' ');
end;
write(' #');
writeln;
end;
writeln('=====================
end;
begin
legend2;
X:=2;
Y:=17;
GotoXY(X, Y);
textbold;
write(' Откуда: ');
textnormal;
read(leave);
while (leave<'a') or (leave>n) do begin {проверка на дурака}
write('# Введенные данные не входят в диапозон. Повторите ввод "откуда": ');
read(leave);
end;
write('#');
textbold;
write(' Куда: ');
textnormal;
read(dest);
while (dest<'a') or (dest>n) do begin {проверка на дурака}
write('# Введенные данные не входят в диапозон. Повторите ввод "куда": ');
read(dest);
end;
write('#');
textbold;
write(' Количство ребер: ');
textnormal;
read(kolvo);
while (kolvo<0) do begin {проверка на дурака}
write('# Число ребер не может быть меньше 0. Повторите ввод "кол-во ребер": ');
read(kolvo);
end;
clrscr;
matr2:=matr; {кратчайший путь}
for c:=1 to kolvo-1 do matr2:=mnozh(matr,matr2);
if matr2[leave,dest]=0 then begin {если путь не найден}
gotoxy(1,1);
writeln('=====================
write('#');
textbold;
writeln(' Пути нет.');
textnormal;
end
else begin
if kolvo=1 then begin {за одно ребро}
gotoxy(1,1);
writeln('=====================
write('#');
textbold;
writeln(' Кратчайший путь из ',kolvo,' ребра из ','"',leave,'"',' в ','"',dest,'"',' будет путь длиной ',matr2[leave,dest],'.');
textnormal;
end
else begin {за несколько и больше ребер}
gotoxy(1,1);
writeln('=====================
write('#');
textbold;
writeln(' Кратчайший путь из ',kolvo,' ребер из ','"',leave,'"',' в ','"',dest,'"',' будет путь длиной ',matr2[leave,dest],'.');
textnormal;
end;
end;
writeln('# Наикратчайшая матрица:');
vivod(matr2);
matr2:=matr;
for c:=1 to kolvo-1 do matr2:=mnozh2(matr,matr2);
if matr2[leave,dest]<>0 then begin {путь найден}
if kolvo=1 then begin {за одно ребро}
write('#');
textbold;
writeln(' Наидлиннейший путь из ',kolvo,' ребра из ','"',leave,'"',' в ','"',dest,'"',' будет путь длиной ',matr2[leave,dest],'.');
textnormal;
end
else begin {за несколько и больше ребер}
write('#');
textbold;
writeln(' Наидлиннейший путь из ',kolvo,' ребер из ','"',leave,'"',' в ','"',dest,'"',' будет путь длиной ',matr2[leave,dest],'.');
textnormal;
end;
end;
writeln('# Наидлиннейшая матрица: ');
vivod(matr2);
readln;
end;
3.1.2. Блок-схема процедуры реализации метода Шимбелла.
3.1.3.
Таблица тестов.
Критерии черного ящика.
Минимально-грубое тестирование (МГТ).
Информация о работе Программа определения кратчайшего пути в графе