Міністерство освіти і науки України Вінницький національний технічний університет Кафедра КН Лабораторна робота №5 з дисципліни «Дискретна математика» Тема: «: Побудова найкоротшого шляху у графі» Виконали: студенти групи 2КН – 15б Ваховський В.М. Ільченко О.В. Перевірила: Ваховська Л. М. Вінниця 2016 Мета роботи: Набути навичок побудови найкоротшого шляху в зваженому графі за допомогою хвильового алгоритму і алгоритму Дейкстри. Завдання: розробити алгоритм та програму для алгоритму Дейкстри. Продемонструвати роботу програми на прикладі. 3. Завдання для виконання Варіант 3 / Варіант 7 / Схема алгоритму / Рисунок 1 – Блок-схема алгоритму Дейкстри Результати роботи: Варіант 7 / Рисунок 2 – Результат роботи програми для алгоритму Дейкстри Варіант 3 / Рисунок 3 – Результат роботи програми для алгоритму Дейкстри Висновок Під час виконання лабораторної роботи було розроблено алгоритм Дейкстри. Було розроблено програму для знаходження мінімального шляху графу. Продемонстровано результати роботи програми. Додаток 1. Інструкція користувача Для запуску програми мінімізації функції необхідно запустити файл Algoritm_Dijkstra.exe. Ввести вектор або функцію. Натиснути на кнопку «Найти кратчайший путь» для виконання пошуку мінімальної форми. Програма виведе найкоротший шлях та загальну вагу. Додаток 2. Лістинги програми //--------------------------------------------------------------------------- #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; //--------------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <iostream> #include <string.h> #include <math.h> #include <vcl.h> #pragma hdrstop //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ class minterm { public: int a[4]; int size; minterm(){ size=0; } minterm(int A,int B,int C,int D){ size=4; a[0]=A; a[1]=B; a[2]=C; a[3]=D; } void fill(int A,int B,int C,int D){ a[0]=A; a[1]=B; a[2]=C; a[3]=D; } bool operator == (const minterm &m){ for(int i=0;i<size;i++){ if(a[i]!=m.a[i]) return 0; } return 1; } bool operator != (const minterm &m){ for(int i=0;i<size;i++){ if(a[i]!=m.a[i]) return 1; } return 0; } bool not_void(){ for(int i=0;i<size;i++){ if(a[i]!=-1) return 1; } return 0; } bool include(const minterm &m) { for(int k=0;k<4;k++) { if(m.a[k]!=-1 && a[k]!=m.a[k]) return 0; } return 1; } int count_1() { int c=0; for(int i=0;i<4;i++) if(a[i]==1) c++; return c; } bool positions_coincide(const minterm &m) { for(int i=0;i<4;i++) if(a[i]==-1 && a[i]!=m.a[i]) return 0; return 1; } bool can_be_united(const minterm &m) { for(int k=0;k<4;k++) { if(a[k]!=m.a[k]) { for(int i=k+1;i<4 && k<3;i++) if(a[i]!=m.a[i]) return false; return true; } } return true; } void glue(const minterm &m) { for(int k=0;k<4;k++) { if(a[k]!=m.a[k]) { for(int i=k+1;i<4 && k<3;i++) if(a[i]!=m.a[i]) return; a[k]=-1; return; } } } AnsiString print(){ AnsiString s; if(!(a[0]==-1 && a[1]==-1 && a[2]==-1 && a[3]==-1)){ if(a[0]==1) s=s+"A"; if(a[0]==0) s=s+"!A"; if(a[1]==1) s=s+"B"; if(a[1]==0) s=s+"!B"; if(a[2]==1) s=s+"C"; if(a[2]==0) s=s+"!C"; if(a[3]==1) s=s+"D"; if(a[3]==0) s=s+"!D"; } return s; } }; //--------------------------------------------------------------------------- class fal{ public: minterm *mdnf; int size,param; class Table; fal(){ size=0; mdnf=0; param=0; } fal(const AnsiString s,int param_){ minterm table[16]={ minte...