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


 

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

57601. ДЕРЖАВА З ЦЕНТРОМ У КИЄВІ. ПЕРШІ КНЯЗІ 94.5 KB
  І хоч Рюрик уже помер а його син Ігор поскандінавському Інґвар був ще замолодим щоб стати на чолі дружини Олег що був регентом опікуном доки Ігор не досягне повноліття зібрав дружину з варягів словян та фіннів узяв із собою Ігоря й поплив до Києва.
57602. Сталінська індустріалізація України. Друга і третя п’ятирічки 1.09 MB
  Мета уроку: Освітня: Визначити протиречиві тенденції 30х років Уяснити що друга і третя пятирічки були важливим етапом індустріалізації визначити дати другої та третьої пятирічок Визначити хронологічну послідовність головних подій...
57603. Україна – наш спільний дім 42 KB
  Обладнання: відеоматеріали: уривок з реклами Я їду додому адміністративна карта України фізична карта України; фотографії видатних людей вихідців з України; аудіозаписи пісен: С чего начинается Родина Україна у виконанні...
57604. Другий зимовий похід армії УНР. Припинення боротьби регулярних українських військ за незалежність України 59 KB
  Мета: проаналізувати мету та причини поразки Другого зимового походу армії УНР; пояснити значення Другого зимового походу як останньої збройної спроби відвоювати самостійність України та наслідки невдачі акції.
57605. Київська держава наприкінці Х – у першій половині ХІ ст 196.5 KB
  Відповідає та команда у якої швидше буде готова відповідь. За кожний правильний термін команда отримує 1 бал. Перша команда літера К. Друга команда літера С.
57606. Про що можна довідатися з сімейного фотоальбому. Родинне дерево 167 KB
  Мета: розкрити зміст науки генеалогія значення поняття родинне дерево; розвивати вміння роботи з фото джерелами створювати родинне дерево та визначити їх роль у роботі дослідників...
57608. Возникновение Запорожской Сечи 120 KB
  Уметь доказать что казачество явление мировой истории. Воспитать в себе чувство гордости за свой народ породивший такую силу как казачество. Казачество как явление мировой истории. Домашнее задание: Подобрать материал доказывающий что казачество мировое явление.
57609. Передумови та початок національно-визвольної війни українського народу в середині XVII ст 288 KB
  Мета: зясувати передумови причини та характер війни; розкрити роль Богдана Хмельницького в підготовці та початку національновизвольної війни; розвивати вміння учнів аналізувати історичні джерела працювати над вивченням історичних подій за алгоритмом працювати самостійно з довідковою літературою...