43455

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

Курсовая

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

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

Русский

2013-11-05

102.5 KB

4 чел.

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


 

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

64697. Попроцессный метод учета затрат и калькулирования 216 KB
  Наибольший удельный вес во всех расходах предприятий занимают затраты на производство продукции. Совокупность производственных затрат показывает во что обходится предприятию изготовление выпускаемой продукции...
64698. Статистические методы анализа доходов от основных операций банка 1.75 MB
  К числу основных показателей денежных вкладов относятся: средний размер вклада оборачиваемость вкладного рубля эффективность вкладных операций. Его рассчитывают делением суммы остатка вкладов на количество лицевых счетов вкладов.
64700. Пути снижения издержек производства и реализации продукции на примере предприятия ОАО «Хлебокомбинат» г. Обнинск 771.5 KB
  Актуальность выбранной темы обусловлена тем, что учет затрат – важнейший инструмент управления предприятием. Знание затрат на производство, анализ этих затрат позволяет гибко регулировать производственный процесс.
64701. Совершенствование методики учета затрат и калькулирования себестоимости продукции 123 KB
  Теоретические и методологические основы калькулирования себестоимости продукции. Калькулирование себестоимости продукции роль калькулирования в управлении производством. Принципы калькулирования себестоимости продукции.
64702. Учет нематериальных активов 2.04 MB
  Кроме того, к нематериальным активам могут относиться организационные расходы (расходы, связанные с образованием юридического лица, признанные в соответствии с учредительными документами вкладом участников (учредителей) в уставный (складочный) капитал), а также деловая репутация организации.
64703. РАСХОДЫ НА ФИНАНСИРОВАНИЕ БЮДЖЕТНЫХ ИНВЕСТИЦИЙ 495 KB
  Целью данной работы является рассмотрение и изучение проблем и возможностей улучшения формирования расходов на финансирование бюджетных инвестиций. Задачи исследования: изучить теоретические основы бюджетных инвестиций; – изучить формы государственного финансирования экономики...
64704. Доходах и расходах государственного бюджета 852.5 KB
  Понятие государственного бюджета понятие расхода и дохода государственного бюджета. Так в практической части данной работе рассматривается влияние доходов государственного бюджета на расходы государственного бюджета.