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


 

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

77847. Социально-философский смысл евразийства 191.5 KB
  Славянофилы ставшие основоположниками теории локальных цивилизаций в России старались возродить религиозную философию истории и на ее теоретической основе создать образ России единственной после Византии цивилизации усвоившей высшую религию - христианство в наиболее...
77848. Тепловые машины 148.5 KB
  Настоящая история паровых машин начинается лишь в 17 веке. Одним из первых, кто создал действующий прообраз паровой машины, был Дени Папен. Паровая машина Папена, была фактически лишь набросками, моделью. Он так и не сумел создать настоящую паровую машину, которая могла бы использоваться на производстве.
77849. Смоляне – защитники Отечества 132 KB
  В этом реферате будет говориться только о смолянах. Моя цель работы - рассказать вам все про смолян. Как они защищали нашу Родину, как они боролись, как они достойно погибали... И про то, как мы их не забудем никогда!
77850. Развитие политической мысли на Руси и в России 145.5 KB
  Особенность политической мысли России заключается в разработке следующих проблем: создании и развитии русской государственности выяснения специфики исторического пути России и составляющих ее народов поиск идеала общественного устройства...
77851. Сущность и функции рынка 124.5 KB
  Рынок как экономический механизм формировался на протяжении тысячелетий в течение которых менялось и содержание самого понятия. В общем виде понятие рынок это система экономических отношений складывающихся в процессе производства обращения и распределения товаров а также движения денежных средств.
77852. Основания и условия возникновения деликтных обязательств 27.5 KB
  Основания и условия возникновения деликтных обязательств Деликтные представляют собой обязательства которые возникают вследствие причинения вреда субъектами отношений из внедоговорных отношений и требуют полное возмещение за счет средств причинителя вреда или иных лиц на которых законом возложена обязанность возмещения вреда. отношения; возникают в нарушении прав которые носят абсолютный характер...
77853. Ответственность за вред, причиненный ИПО 27 KB
  Ответственность за вред причиненный ИПО К таковым относятся ТС механизмы электрическая энергия высокого напряжения атомная энергия взрывчатые вещества сильнодействующие яды. ИПО определенные предметы материального мира проявляющие в процессе деятельности по их использованию эксплуатации вредоносность не поддающуюся или не в полной мере поддающуюся контролю человека в результате чего они создают опасность для окружающих. Ответственность за вред несет владелец. Не признается владельцем и не несет ответственности за вред...
77854. Ответственность за вред, причиненный н/л 29 KB
  Ответственность за вред причиненный н л Причиненный до 14 возлагается на его родителей усыновителей или опекунов либо на соответствующее учреждение юридическое лицо если малолетний находился в нем или был под его надзором во время причинения вреда. Родители усыновители и опекуны отвечают за вред причиненный малолетними при наличии общих оснований деликтной ответственности: противоправность причинно-следственная связь вина. Причиненный от 14 до 18 самостоятельно несут ответственность за причиненный вред на общих основаниях. В...
77855. Особенности возмещения вреда при повреждении здоровья и причинения смерти гражданину 29 KB
  Однако результатом причиненного здоровью потерпевшего вреда может стать и стойкая или невосстановимая утрата им трудоспособности. Учитывается также грубая неосторожность самого потерпевшего содействовавшая возникновению или увеличению вреда. При этом размер возмещения уменьшается пропорционально степени вины потерпевшего. В случае смерти потерпевшего имущественные потери возникают у близких ему лиц которых он полностью или частично содержал при жизни будучи их кормильцем а также у лиц понесших расходы на его погребение.