Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Знаходження шляхів графа
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Математика
Група:
ПМ-22
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут прикладної математики
і фундаментальних наук
Кафедра прикладної математики
Лабораторна робота № 2
Знаходження шляхів графа
Львів 2007
Умова задачі:
5.6. Знайти найкоротший шлях від вершини Хi і Хj ( i і j – дві останні цифри номера залікової книжки) графа заданого Х описом:
(1,4; 1,5; 2,13; 2,14; 3,21; 3,25; 4,10; 4,11; 4,12; 5,12; 5,19; 5,20; 6,4; 6,5; 7,13; 7,14; 8,16; 8,18; 18,9; 10,14; 11,16; 11,22; 11,17; 11,18; 12,6; 12,9; 9,13; 15,25; 16,22; 23,17; 15,17; 17,21; 18,23; 18,24; 19,11; 19,17; 19,24; 20,24; 20,21; 20,9; 0,1; 0,11; 0,13; 0,20)
Текст програми:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
//-----------------------------CONSTANTS
const int kilver = 26; //kilkist vershyn
const int q = 2*kilver; //mnogyny Lm
//-----------------------------VARIABLES
matrycya_sumignosti[kilver][kilver]= {
// 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
/*0*/{0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0},
/*1*/{1,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*2*/{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
/*3*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1},
/*4*/{0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*5*/{0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0},
/*6*/{0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*7*/{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
/*8*/{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0},
/*9*/{0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0},
/*0*/{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
/*1*/{1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0},
/*2*/{0,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*3*/{1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*4*/{0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
/*5*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
/*6*/{0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
/*7*/{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0},
/*8*/{0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0},
/*9*/{0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0},
/*0*/{1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
/*1*/{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0},
/*2*/{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
/*3*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0},
/*4*/{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0},
/*5*/{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}};
int mnogyna[q][kilver];
int nevybrani[kilver];
int k; //kilkilst dodanyh v Lm elementiv
int m; //vidpovidae za nomer mnogyny (L(m))
int pathlen=0;
int path[kilver];
int vbegin =6;
int vend =7;
//-------------------------FUNCTION PROTOTYPES
void initialization(void);
void formuvannya_mnogyn(void);
int nalegnist(int j);
void zapys(int j, int m, int k);
void shortway(void);
void vyvid(void);
//--------------------------MAIN
void main(void)
{
clrscr();
initialization();
formuvannya_mnogyn();
shortway();
vyvid();
getch();
}
//-------------------------FUNCTIONS
void initialization(void)
{
for (int i=0; i<kilver ;i++)
{for (int j=0; j<q; j++){mnogyna[i][j]=-1;};nevybrani[i]=-1;}
}
//--------------------
void formuvannya_mnogyn(void)
{
int p; //budem vybyraty vershynu z L(m-1)
int j; //berem reshtu vershyn
mnogyna[0][0]=vbegin;
for(int i=0;i<kilver;i++){if(i==vbegin) nevybrani[i]=i;}
m=1;
do
{
k=0;
for(int i=0; mnogyna[m-1][i]>=0;i++) //vybyraem elementy z poperednyoi
// mnogyny
{
p=mnogyna[m-1][i]; //vybyraem Xp z L(m-1)
for(j=0; j<kilver;j++) //vybyraem Xj - dovilnu vershynu
{
if(matrycya_sumignosti[j][p]==1)//yaksho Xj sumigna z Xp
{
if(nalegnist(j)==0){zapys(j,m,k);k++;};
//yaksho Xj ne nalegyt do Lk, k<=m-1 todi
//formuem mnogynu Lm(zapys Xj)
}
}
}
m++;
}
while (nalegnist(vend)==0);
}
//-------------------
int nalegnist(int j)
{
int ret=0;
for(int i=0;i<kilver;i++)
{if(nevybrani[i]==j){ret=1;}}
return ret;
}
//-------------------
void zapys(int j, int m, int k)
{
int pr=1; //praporec 1-treba zapysuvaty 0 - ne treba
for(int i=0;i<=k;i++)
{if(mnogyna[m][i]==j){pr=0;}};
if(pr==1){mnogyna[m][k]=j;nevybrani[j]=j;};
}
//-------------------
void shortway(void)
{
int xk;
for(int i=0;i<kilver;i++){path[i]=-1;};
path[0]=vend;
pathlen=0;
for (m=m-2;m>=0;m--)
{for(int j=0;mnogyna[m][j]>=0;j++)
{if(matrycya_sumignosti[path[pathlen]][mnogyna[m][j]]==1)
{pathlen++;path[pathlen]=mnogyna[m][j];}
}
}
}
//-------------------
void vyvid(void)
{
cout<<"Shlyah mig vershynamy "<<vbegin<<" i "<< vend<<"\n";
cout<<path[0];
for(int i=1;path[i]>0;i++){cout<<" - "<<path[i];}
cout<<"\nDovgyna shlyahu: L = "<<pathlen;
}
Результат виконання:
Висновок: На лабораторній роботі я навчився знаходити найкоротший шлях у незваженому графі.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора