#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
#define MaxNodes 6
#define B 1000 //Машинный эквивалент бесконечности.
//Описание типа узла стека.
typedef struct Zveno *svqz;
typedef struct Zveno
{
int Element;
svqz Sled;
};
class Spisok
{
private:
int A[MaxNodes][MaxNodes]; //Матрица весов дуг.
int D[MaxNodes]; //Матрица расстояний от источника до
//всех вершин графа.
svqz Stack; //Указатель на рабочий стек.
void UDALENIE (svqz *, int *);
void W_S (svqz *, int);
int Pusto_Q (int *); // к Дейкстре
public:
Spisok() {Stack = NULL;}
void Vvod_Ves();
void Reshenie ();
void Reshenie2 ();
};
//проверка на ввод
int enter(char*str){
char* end_ptr;
bool flag=true;
double arg;
while(flag){
arg = strtod(str, &end_ptr);
if (*end_ptr)
{
cout << "\nНужно ввести цифру, попробуйте еще раз:\n";
cin >> str;
}
else
flag=false;
}
int intArg=(int) arg;
return intArg;
}
void main ()
{setlocale(0,"");
Spisok As;
As.Vvod_Ves();
char*exit = new char [80];
int oper;
cout << "\nВыберите операцию:\n\n"
"1 - Беллмана-Мура\n\n"
"2 - Алгоритм Дейкстры\n\n"
"0 - Выход\n\n";
while(exit[0]!='0'){
cout << "\nВведите цифру, соответствующую нужной операции: ";
char*tempStr=new char[80];
cin >> tempStr;
oper=enter(tempStr);
switch(oper){
case 1:
As.Reshenie();
break;
case 2:
As.Reshenie2();
break;
case 0:
exit[0]='0';
break;
default: cout << "Нет такой операции!\n";break;
}
delete[]tempStr;
}
}
int Spisok::Pusto_Q (int *Q) //Дейкстра
{
for (int i=0;i<MaxNodes;i++)
if ( *(Q+i)!=0 ) return 0; //Ложь - не пусто!
return 1; //Истина - пусто!
}
void Spisok::Reshenie () //Беллмана
{setlocale(LC_ALL,"rus");
int S; // Начальная вершина пути (источник).
int T; // Конечная вершина пути.
int u,v;
int i,j,k;
svqz UkZv;
cout << "Введите начальную вершину: ";
cin >> S; S--;
//Инициализация.
for (i=0;i<MaxNodes;i++) D[i] = A[S][i];
D[S] = 0;
//Вычисление матрицы расстояний от
//источника до всех вершин графа.
for (k=0;k<MaxNodes-2;k++)
for (i=0;i<MaxNodes;i++)
if ( i!=S )
for (j=0;j<MaxNodes;j++)
if ( D[i] > D[j]+A[j][i] ) D[i] = D[j]+A[j][i];
//Вывод матрицы расстояний от источника
//до всех вершин графа.
cout << "Матрица расстояний: \n";
for (i=0;i<MaxNodes;i++) cout << D[i] << " ";
cout << endl;
// -----------------------------------------------------
// Нахождение кратчайшего пути из S в T с использованием
// построенной матрицы расстояний.
// -----------------------------------------------------
cout << "Введите конечную вершину пути: ";
cin >> T; T--;
W_S (&Stack,T); v = T;
while ( v!=S )
{
for (i=0;i<MaxNodes;i++)
if ( D[v]==D[i]+A[i][v] ) u = i;
W_S (&Stack,u);
v = u;
}
//Вывод кратчайшего пути на экран дисплея.
cout << "Кратчайший путь: ";
UkZv = Stack;
while ( UkZv != NULL )
{ cout << UkZv->Element+1 << " ";
UkZv = UkZv->Sled; }
cout << endl;
}
void Spisok::Reshenie2 ()//Дейкстра
{ setlocale(0,"");
int S; // Начальная вершина пути (источник).
int T; // Конечная вершина пути.
int u,v,Min;
int i;
svqz UkZv;
int Q[MaxNodes];
cout << "Введите начальную вершину: ";
cin >> S; S--;
//Инициализация.
for (i=0;i<MaxNodes;i++) { D[i] = A[S][i]; Q[i] = 0; }
D[S] = 0;
for (i=0;i<MaxNodes;i++) Q[i] = 1;
Q[S] = 0;
//Вычисление матрицы расстояний от
//источника до всех вершин графа.
while (!Pusto_Q(&Q[0])) //Пока Q не пусто.
{
Min = B;
for (i=0;i<MaxNodes;i++)
if (Q[i]==1 && D[i]<Min) { Min = D[i]; u = i; }
Q[u] = 0;
for (i=0;i<MaxNodes;i++)
if (Q[i] == 1)
if ( D[i] > D[u]+A[u][i] ) D[i] = D[u] + A[u][i];
}
//Вывод матрицы расстояний от источника
//до всех вершин графа.
cout << "Матрица расстояний: \n";
for (i=0;i<MaxNodes;i++) cout << D[i] << " ";
cout << endl;
// -----------------------------------------------------
// Нахождение кратчайшего пути из S в T с использованием
// построенной матрицы расстояний.
// -----------------------------------------------------
cout << "Введите конечную вершину пути: ";
cin >> T; T--;
W_S (&Stack,T); v = T;
while ( v!=S )
{
for (i=0;i<MaxNodes;i++)
if ( D[v]==D[i]+A[i][v] ) u = i;
W_S (&Stack,u);
v = u;
}
//Вывод кратчайшего пути на экран дисплея.
cout << "Кратчайший путь: ";
UkZv = Stack;
while ( UkZv != NULL )
{ cout << (UkZv->Element+1) << " ";
UkZv = UkZv->Sled; }
cout << endl;
}
void Spisok::Vvod_Ves()
//Ввод матрицы весов дуг заданного графа.
{setlocale(LC_ALL,"rus");
ifstream input_file1("1.txt");
for (int i=0; i<MaxNodes; i++)
{
for (int j=0; j<MaxNodes; j++)
{
input_file1 >> A[i][j];
}
}
for(int i = 0; i < MaxNodes; i++)
{
for(int j = 0; j < MaxNodes; j++)
{
cout<< setw(MaxNodes)<<A[i][j];
if ( A[i][j]==0 ) A[i][j] = B;
}
cout<<endl;
}
}
void Spisok::W_S (svqz *stk, int Elem)
//Помещение Elem в стек stk.
{
svqz q=new (Zveno);
(*q).Element = Elem;
(*q).Sled = *stk; *stk = q;
}
void Spisok::UDALENIE (svqz *stk, int *Klad)
//Удаление звена из стека, заданного указателем *stk.
//Значение информационного поля удаляемого звена сохраня-
//ется в параметре Klad.
{setlocale(LC_ALL,"rus");
svqz q;
if (*stk==NULL) cout<<"Попытка выбора из пустого стека!\n";
else
{ *Klad = (**stk).Element;
q = *stk; *stk = (**stk).Sled; delete q; }
}