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


 

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

73021. ИЗМЕРЕНИЕ ГЕОМЕТРИЧЕСКИХ ПАРАМЕТРОВ ДЕТАЛЕЙ МИКРОМЕТРИЧЕСКИМИ ИНСТРУМЕНТАМИ 1.23 MB
  Особенности конструкции и принцип работы микрометрического инструмента. Навертывая гайку 6 на коническую часть хвостика можно уменьшить осевой люфт микрометрического винта 7 который перемещается внутри стебля по резьбовой поверхности с шагом резьбы.
73022. ПЛОСКОПАРАЛЛЕЛЬНЫЕ КОНЦЕВЫЕ МЕРЫ 479.5 KB
  Инструменты: набор плоскопараллельных концевых мер длины; принадлежности к наборам плоскопараллельных концевых мер. Задание: составить блоки плиток по заданным размерам. Плоскопараллельные концевые меры длины составляют основу современных линейных измерений в машиностроении.
73023. СОЗДАНИЕ ЛОГИЧЕСКОЙ МОДЕЛИ ДАННЫХ В IDEF1X 306 KB
  Она включает сущности и взаимосвязи отражающие основные бизнес-правила предметной области. Такая диаграмма не слишком детализирована в нее включаются основные сущности и связи между ними которые удовлетворяют основным требованиям предъявляемым к ИС.
73024. Ввод, редактирование и форматирование текста в Word 61 KB
  Изучить основные приемы ввода редактирования и форматирования текста; Контрольные вопросы Каково назначение программы Word Как изменить формат слова формат абзаца Как удалить ненужную часть текста Как изменить параметры страницы Как переместить и скопировать текст...
73025. Работа с таблицами в Word 130 KB
  Таблица представляет собой сетку из столбцов и строк, образующих ячейки, в которые можно поместить тексты и рисунки. Небольшие таблицы создают с помощью кнопки Добавить таблицу на панели инструментов
73026. Ввод, форматирование данных и составление формул 126 KB
  Цель работы: С помощью команды Формат Ячейки отформатируйте данные столбца D денежным форматом без десятичных разрядов. С помощью кнопки Формат по образцу скопируйте формат столбца D в E. Кнопками панели Форматирования задайте в столбце F процентный формат с двумя разрядами после запятой.
73027. Построение и редактирование диаграмм в Excel 160 KB
  Научиться строить диаграммы с помощью Мастера; Научиться редактировать диаграммы. Контрольные вопросы Каково назначение диаграмм Какие виды диаграмм вам известны Как построить диаграмму на отдельном листе Как изменить тип диаграммы Как удалить диаграмму...
73028. Моделирование файловых систем 147.5 KB
  Пользователи дают файлам символьные имена при этом учитываются определенные ограничения ОС. В каталоге содержится список файлов входящих в него и устанавливается соответствие между файлами и их характеристиками атрибутами.
73029. Визначення структурно-фазового складу НВМ, що містить ВНТ, методами рентгенівської дифракції та електронної мікроскопії 1.5 MB
  Визначити структурно-фазовий склад НВМ що містить ВНТ за даними рентгенівської дифракції та електронної мікроскопії. Дослідити зміну структурнофазового складу НВМ в процесі термохімічної обробки.