43455

Исследование и программная реализация методов и алгоритмов теории графов

Курсовая

Информатика, кибернетика и программирование

Расчетно-графическая работа представляет собой решение задачи по нахождению минимального пути в графе из заданной вершины x в заданную вершину y, содержащего не более чем k дуг. Расчет выполнен с помощью языка программирования Pascal 7.1 на ПК Pentium3.

Русский

2013-11-05

102.5 KB

6 чел.

10

Министерство образования Российской Федерации

ГОУВПО”Сибирский государственный технологический университет”

Кафедра cистемотехники

ДИСКРЕТНАЯ МАТЕМАТИКА

ИССЛЕДОВАНИЕ
МЕТОДОВ И АЛГОРИТМОВ ТЕОРИИ ГРАФОВ

Курсовая работа

Пояснительная записка

(СТ.000000.005.ПЗ)

                                                                                                         Руководитель  

                                                                                                          Иванилова Т.Н.

                                                                                               _______________________

                                                                                                          дата          оценка        роспись      

                                                                                                          Выполнил

                                                                                                           Студент группы 21-6

                                                                                           Швацкий А.В.

                                                                                           ___________________

                                                                                           дата сдачи                роспись

Сибирский государственный технологический университет

Кафедра системотехники

ЗАДАНИЕ

НА КУРСОВУЮ РАБОТУ ПО ДИСКЕТНОЙ  МАТЕМАТИКЕ

Студент        Швацкий Андрей Вячеславович

Факультет    ФАИТ Группа 21-6

Тема: Исследование и программная реализация методов и алгоритмов теории графов.

Вариант 37

Алгоритм Форда-Беллмана нахождения минимального пути в графе из заданной вершины x  в заданную вершину y, содержащего не более чем k дуг.

Предложенную задачу сформулировать в терминах теории графов и подобрать соответствующий алгоритм.

Реализовать выбранный алгоритм на языке Pascal, использовать представление графа списками. Предусмотреть возможность ввода разнообразных входных данных.

Окончательный вариант программы обязательно должен отображать смысловую постановку задачи.

Приложить распечатки экранов.  

Календарный план выполнения работы

1 – 5.04.01 -        формализация задачи

6 – 10.04.01 -           уточнение входной и выходной информации

11 – 18.04.01 -         составление схемы алгоритма

19 – 30.04.01 -         проведение расчетов

1 – 10.05.01 -        отладка и тестирование

11 – 20.05.01 -        оформление пояснительной записки

23.05.01 – защита курсовой

                                                   Задание выдано____01.04.01

                                                             Руководитель____________ Иванилова Т.Н.                                         

                                                         

Содержание

Реферат

Введение

  1.  Алгоритм Форда-Беллмана
  2.  Решение задачи
    1.  Входная и выходная информация
    2.  Схема алгоритма
    3.  Текст программы
    4.  Протокол контрольного расчета
  3.  Инструкция по работе с программой

Заключение

Список использованных источников

Реферат

Расчетно-графическая работа представляет собой решение задачи по нахождению минимального пути в графе из заданной вершины x  в заданную вершину y, содержащего не более чем k дуг. Расчет выполнен с помощью языка программирования Pascal 7.1 на ПК Pentium3.

 

2. Программа и используемые процедуры.

uses crt,Graph,RGR_Unit;

const

     INF = 100000000; {бесконечность}

     PI=3.1415;

     OZx=350;

     OZy=170;

     R_ver=15;

type LType = array [1..15, 0..14] of real;

    PathType = array [1..15] of integer;

    SWC = array [1..15,1..15] of real;

var

    C: SWC;

{ чтение данных }

procedure GetMatrix(n:integer);

var i,j,g :integer;

begin

  for i := 1 to n do {заполнение матрицы бесконечностями для i<>j иначе 0}

     for j := 1 to n do

        if i = j then C[i,j] := 0 else C[i,j] := INF;

  g:=5;

  for i:=1 to n do

      begin

           for j:=1 to n do

               begin

                    gotoxy(4+j*4,g);

                    read (C[i,j]);

                    if C[i,j]=0 then C[i,j]:=inf;

               end;

           readln;

           g:=g+1;

      end;

end;

{создание матрицы L для начальной вершины v1}

procedure MakeL(v1,n:integer; var L:Ltype);

var i, j, k: integer;

   min: real;

begin

  for i := 1 to N do if i=v1 then L[i,0] := 0 else L[i,0] := INF;

  for k := 1 to n-1 do begin

     for i := 1 to n do begin

        min := INF;

        for j := 1 to n do

           if L[j,k-1]+C[j,i] < min then min:=L[j,k-1]+C[j,i];

        if (i = v1) and (min >0) then min := 0;

        L[i,k] := min;

     end;

  end;

end;

{  поиск пути из v1 в v2 методом Форда-Беллмана

 L - матрица для начальной точки v1

 путь записывается в P (v2 - маркер конца пути,v1 в начале пути не ставится)

 результат функции - длина пути (или INF если пути нет)}

function FindPath(v1, v2,n:integer; var L:LType; var P:PathType) : real;

var

  i,j,k:integer;

begin

  if L[v2, n-1] >= INF then begin

     FindPath := INF;

     exit;

  end;

  k := n-1;

  while (k>0) and (L[v2,k] = L[v2, k-1]) do

     dec(k);

  FindPath := L[v2,k];

  P[k]:=v2;

  while k-1>0 do begin

     i := 1;

     while (i<=n) and (L[i,k-1] + C[ i, P[k] ] <> L[P[k],k]) do inc (i);

     P[k-1] := i;

     dec(k);

  end;

end;

var L:LType;

   len:real;

   Path:PathType;

   gd,gm,i,j,k,n,q,ik,ij:integer;

   Ver_x,Ver_y : array[1..15] of Integer;

   r,dx,dy,dlx,dly,ii,kk : Integer;

   alfa,alfa_i : Real;

   ch : Char;

   p,p1 : String;

begin

  window (0,0,80,25);textbackground(11);clrscr;

  windows4(10,5,56,12,5,15);

  writeln;

  writeln ('Нахождение минимального пути между всеми вершинами');

  writeln ('     нагруженного орграфа с помощью алгоритма');

  writeln;

  writeln ('               Форда- Беллмана');

  gotoxy (5,9);

  writeln ('   Выполнил: студент гр. 21-6 Сорокин  ');

  readln;

  window (2,2,78,24);textbackground(3);clrscr;

  windows4 (10,2,50,4,1,15);

  write ('Введите количество вершин -> ');

  readln (n);

  window (2,2,78,24);textbackground(3);clrscr;

  {windows4 (10,4,52,18,1,15);}

  writeln ('          Введите матрицу длин дуг');

  writeln ('           (для бесконечности 0)');

  gotoxy (4,4);

  write ('    ');

  for i:=1 to n do

      write (i,'    ');

  q:=5;

  for i:=1 to n do

  begin

      gotoxy (3,q);

      writeln (i);

      q:=q+1;

  end;

  gotoxy (4,5);

  GetMatrix(n);

  {windows4 (2,6,70,18,10,15);}

  writeln ('                     Все минимальные пути');

  for i:= 1 to n do begin

     MakeL(i,n,L);

     for j:=1 to n do begin

       len := FindPath(i,j,n,L,Path);

       if (len < INF) And (Len<>0)then begin

           write('Длина=',len:3:0,' Путь: ',i:4);

           k:=1; while Path[k]<>j do begin write(Path[k]:4); inc(k); end;

           write(j:4);

           writeln;

       end;

     end;

  end;

  writeln('Нажмите ВВОД! Появится изображение ОРГРАФа');Readln;

{ Графическое представление ОрГрафа  }

 gd:=ega; gm:=egahi; InitGraph(gd,gm,'');

{ n:=15;

 for i:=1 to n do  for j:=1 to n do

     if i>j then C[i,j]:=1 else C[i,j]:=0;}

 r:=(21*n+(16-n)*3) div 2;

 alfa:=2*PI/n;

{  Определение вершин }

 for i:=1 to n do begin

    alfa_i:=PI-alfa*(i-1);

    Ver_x[i]:=OZx+trunc(1.5*r*cos(alfa_i));

    Ver_y[i]:=OZy+trunc(r*sin(alfa_i));

 end; {i}

{  Изображение связей }

 repeat

 ClearDevice;

 SetBkColor(1);

 p:='Г Р А Ф  по ФОРДУ - БЕЛЛМАНУ ';

 SetTextStyle(0,0,1);

 OutTextXY(10,5,p);

 for i:=1 to n do

    for j:=1 to n do begin

       if C[i,j]<inf then begin

         dx:=Ver_x[j]-Ver_x[i]; dy:=Ver_y[j]-Ver_y[i];

         if C[j,i]<inf then begin

            SetColor(White); Line(Ver_x[i],Ver_y[i],Ver_x[j],Ver_y[j]);

         end

         else begin  dlx:=dx div 2; dly:=dy div 2;

               SetColor(Green); Line(Ver_x[i],Ver_y[i],Ver_x[i]+dlx,Ver_y[i]+dly);

               SetColor(Red); Line(Ver_x[i]+dlx,Ver_y[i]+dly,Ver_x[j],Ver_y[j]);

         end;

       end;

    end;

{ Изображение вершин }

 for i:=1 to n do begin

    SetColor(White);

    for j:=1 to R_ver-1 do Circle(Ver_x[i],Ver_y[i],R_ver-j);

    SetColor(Red); Circle(Ver_x[i],Ver_y[i],R_ver);

    SetColor(Blue);str(i:2,p);

    OutTextXY(Ver_x[i]-7,Ver_y[i]-4,p);

 end; {i}

{  Рисование минимального пути по двум вершинам}

 SetColor(Red);

 OutTextXY(10,32,'Укажите начальную вершину:');

 Window(30,3,35,5);

 GotoXY(1,1);  Readln(i);

 OutTextXY(10,45,'       и конечную вершину:');

 GotoXY(1,2);  Readln(j);

 SetColor(White);

 kk:=0;  MakeL(i,n,L);

       len := FindPath(i,j,n,L,Path);

       if (len < INF) And (Len<>0)then begin

           kk:=1; { Индикатор наличия пути }

           Str(len:3:0,p); Str(i:4,p1);

           OutTextXY(5,75,'Длина='+p+' Путь: '+p1);

           k:=1; ik:=i;

           while Path[k]<>j do begin

              SetColor(Yellow);

              Line(Ver_x[ik],Ver_y[ik],Ver_x[Path[k]],Ver_y[Path[k]]);

              SetColor(Red);

              for ij:=1 to R_ver-1 do Circle(Ver_x[ik],Ver_y[ik],R_ver-ij);

              SetColor(White); Circle(Ver_x[ik],Ver_y[ik],R_ver);

              Str(ik:2,p); OutTextXY(Ver_x[ik]-7,Ver_y[ik]-4,p);

              ik:=Path[k];

              Str(Path[k]:4,p);

              OutTextXY(140+10*k,75,p); inc(k);

           end;

           SetColor(Yellow);

           Line(Ver_x[ik],Ver_y[ik],Ver_x[j],Ver_y[j]);

           SetColor(Red);

           for ij:=1 to R_ver-1 do Circle(Ver_x[ik],Ver_y[ik],R_ver-ij);

           SetColor(White); Circle(Ver_x[ik],Ver_y[ik],R_ver);

           Str(ik:2,p);  OutTextXY(Ver_x[ik]-7,Ver_y[ik]-4,p);

           SetColor(Red);

           for ij:=1 to R_ver-1 do Circle(Ver_x[j],Ver_y[j],R_ver-ij);

           SetColor(White); Circle(Ver_x[j],Ver_y[j],R_ver);

           Str(j:2,p);  OutTextXY(Ver_x[j]-7,Ver_y[j]-4,p);

           Str(j:4,p); OutTextXY(140+10*k,75,p);

       end;

 if kk=0 then  OutTextXY(10,60,'Минимального пути  НЕТ ! ')

 else   OutTextXY(10,60,'  Минимальный путь');

 OutTextXY(10,300,'  ESC  - В Ы Х О Д ');

 ch:=readkey;

 until ch=#27;

  CloseGraph;

end.

{===============================Unit My_Unit===============================}

unit RGR_Unit;

interface

        uses crt,graph;

        procedure windows1;

        procedure windows2;

        procedure windows3(l:string);

        procedure windows4 (x,y,a,b,c1,c2:integer);

        procedure windows5 (x,y,a,b,c1,c2:integer);

        function stepen (x,y:real):real;

        Procedure Menu (s1,s2,s3:string );{меню в графическом режиме}

        Procedure Mouse_Status (x,y:integer;lb:boolean;Var d:Integer );

implementation

{Процедура рисует окошко (небольшое)}

procedure windows1;

         begin

              window (0,0,80,25);textbackground (11);clrscr;

              textcolor (14);

              window (22,6,62,10);textbackground (0);clrscr;

              window (20,5,60,9);textbackground(1);clrscr;

         end;

procedure windows2;{аналогично windows1, только в другом месте ;-)}

         begin

              textcolor (14);

              window (22,15,62,19);textbackground (0);clrscr;

              window (20,14,60,18);textbackground(1);clrscr;

         end;

procedure windows3;{А это окно почти на весь экран, да еще и с рамкой!}

         var i:integer;

         begin

              window (0,1,80,24);textbackground (11);clrscr;

              textcolor (14);

              window (6,4,76,23);textbackground (0);clrscr;

              window (4,3,74,22);textbackground(1);clrscr;

              textcolor(15);

              gotoxy(2,1);write('╔');

              gotoxy(70,1);write('╗');

              gotoxy(70,20);write('╝');

              gotoxy(2,20);write('╚');

              for i:=3 to 69 do

                  begin

                       gotoxy (i,1);write('═');

                       gotoxy (i,20);write('═');

                  end;

              for i:=2 to 19 do

                  begin

                       gotoxy(2,i);write('║');

                       gotoxy(70,i);write('║');

                  end;

              textbackground (1);

              window (6,4,74,23);

              textcolor(14);

              writeln (l);

              textcolor (15);

               for i:=1 to 67 do

                  begin

                       gotoxy(i,2);write('─')

                  end;

              textbackground (1);

              window (8,6,70,21);

              textcolor(14);

         end;

{================================================================================

{------------------------раздвигающееся окошко-------------------------------}

procedure windows4;

         var i,j,k:integer;

         begin

         window (0,0,80,25); textbackground(11);clrscr;

         window (0,0,80,25);clrscr;

           for i:=round(a/2) downto 0 do

           begin

             textcolor(c2);

             window (x+2+i,y+1,x+a+2-i,y+b+1);textbackground(0);clrscr;

             window (x+i,y,x+a-i,y+b);textbackground(c1);clrscr;

             delay(60);

           end;

           gotoxy(2,1);write('╔');

           gotoxy(a,1);write('╗');

           gotoxy(a,b+1);write('╝');

           gotoxy(2,b+1);write('╚');

           for j:=3 to a-1 do begin gotoxy(j,1);write('═');gotoxy(j,b+1);write('═');end;

           for j:=2 to b do begin gotoxy(2,j);write('║');gotoxy(a,j);write('║');end;

           window (x+3,y+1,x+a-4,y+b-1);textbackground(c1);clrscr;

         end;

{==========================================================================}

{------------------------Аналогично Windows4-------------------------------}

procedure windows5;

         var i,j,k:integer;

         begin

           for i:=round(a/2) downto 0 do

           begin

             textcolor(c2);

             window (x+2+i,y+1,x+a+2-i,y+b+1);textbackground(0);clrscr;

             window (x+i,y,x+a-i,y+b);textbackground(c1);clrscr;

             delay(60);

           end;

           gotoxy(2,1);write('╔');

           gotoxy(a,1);write('╗');

           gotoxy(a,b+1);write('╝');

           gotoxy(2,b+1);write('╚');

           for j:=3 to a-1 do begin gotoxy(j,1);write('═');gotoxy(j,b+1);write('═');end;

           for j:=2 to b do begin gotoxy(2,j);write('║');gotoxy(a,j);write('║');end;

           window (x+3,y+1,x+a-4,y+b-1);textbackground(c1);clrscr;

         end;

{------------------------------------------------------------------------}

function stepen;{Данная функция вычисляет степень числа.

                (Первый параметр- число, второй- степень, в которую возво-

                дим данное число)                                             }

        begin

             stepen:=exp(y*ln(x));

        end;

{==========================================================================}

{---------------------меню в графическом режиме----------------------------}

Procedure Menu (s1,s2,s3:string ); {Меню сосотоит из трех пунктов (s1, s2, s3)}

Begin

    SetTextStyle (0,0,2);

    OutTextXY (240,160,s1);

    OutTextXY (275,200,s2);

    OutTextXY (280,240,s3);

End;

{==========================================================================}

{---------------Определение положения мышки для меню-----------------------}

Procedure Mouse_Status (x,y:integer;lb:boolean;Var d:Integer );

Begin

    if (lb) and (x>=242) and (x<=396) and (y>=163) and (y<=174) then d:=1;

    if (lb) and (x>=277) and (x<=368) and (y>=204) and (y<=214) then d:=2;

    if (lb) and (x>=282) and (x<=357) and (y>=244) and (y<=255) then d:=3;

End;

{==========================================================================}

End.

{==============================END MODUL=====================================}

3. Элементы программы выводимые на экран

При запуски программы появляется меню,  состоящее из следующих подпунктов:

  •  Введите количество вершин;
  •  Введите матрицу длин дуг;
  •  Изображение орграфа;
  •  Нахождение минимального пути;

После ввода количества вершин вводим размерность матрицы.

   

   Введите матрицу длин дуг

           (для бесконечности 0)

       1    2    3    4

  1

  2

  3

  4

Рис. 1 Ввод матрицы

Далее, после ввода матрицы заходим в пункт «изображение орграфа» и нахождение минимального пути».

                                                                                

                                                                                

Рис. 2 Изображение орграфа.

4. Список использованных источников

  1.  Иванилова Т.Н., Крайченкова О.В. Дискретная матаматика. Сборник заданий с примерами решений. Красноярск: СибГТУ, 2000. – 47с.

  1.  Приложение: Turbo Pascal 7.0


 

А также другие работы, которые могут Вас заинтересовать

70218. УГОЛОВНО-ИСПОЛНИТЕЛЬНОЕ ПРАВО 217 KB
  Уголовно-исполнительная политика направление деятельности государства в его специально уполномоченных органах в сфере исполнения уголовного наказания. Уголовно-исполнительная политика определяет: цели; принципы; стратегию; основные направления формы методы деятельности...
70219. Фотокомпозиция 77.5 KB
  Композиция – построение, группировка и последовательность изобразительных приёмов, организующих идейно-художественное целое; соотношение и взаимное расположение частей. Точка съёмки – это положение фотоаппарата по отношению к снимаемому объекту. Ниже приведена классификация точки съемки.
70220. Введение в фотографию 103.5 KB
  Развитие на нынешнем этапе цифровой фотографии происходит в основном благодаря электронным и информационным технологиям. Принцип действия фотографии основан на получении изображений и фиксировании их с помощью химических и физических процессов получаемых с помощью света...
70221. Основы теории цвета 86.5 KB
  Индивидуальное восприятие цвета определяется его спектральным составом а также цветовым и яркостным контрастом c окружающими источниками света а также несветящимися объектами. Накопленные экспериментальные данные в XX веке по волновым и корпускулярным свойствам видимого...
70222. Принципы работы фотоаппаратов 95.5 KB
  Численное значение диафрагмы определяет следующие элементы фотографического процесса: экспозиция с уменьшением отверстия на одну ступень поток света уменьшается вдвое что требует увеличения вдвое времени выдержки для сохранения правильной экспозиции; глубина резкости чем меньше отверстие...
70223. Основні терміни метрології та їх визначення 311 KB
  Фізичні величини та одиниці вимірювань Обєкти довкілля це фізичні тіла та їх системи. Вибір основних величин і розмірів їх одиниць під час побудови системи одиниць теоретично довільний але він продиктований певними вимогами практики а саме: кількість основних величин має бути невеликою...
70224. Методологические и правовые основы безопасности жизнедеятельности 332.5 KB
  Студент должен знать: ПК50 основы безопасности общества и личности; порядок взаимодействия медицинских формирований и учреждений при ликвидации последствий в очагах поражения ПК12 особенности организации оказания медицинской помощи проведения реанимационных мероприятий в чрезвычайных...
70225. ЗАЩИТА ЧЕЛОВЕКА ОТ ВРЕДНЫХ И ОПАСНЫХ ФАКТОРОВ ПРИРОДНОГО И ТЕХНОГЕННОГО ПРОИСХОЖДЕНИЯ 887.5 KB
  Цель занятия: овладеть следующими компетенциями в пределах дисциплины БЖД и Медицина катастроф ПК12 способность и готовность использовать методы оценки природных и медико-социальных факторов среды в развитии болезней у взрослого населения и подростков проводить их коррекцию осуществлять...
70226. Безопасность жизнедеятельности в медицинских организациях 364 KB
  Система здравоохранения сегодня - это более трех миллионов работающих, тысячи медицинских организаций (лечебно-профилактических, аптечных, санитарно-эпидемиологических учреждений) десятки научно-исследовательских институтов, центров, высших и средних учебных заведений...