#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;}
~Spisok() {};
void Vvod_Ves();
void Reshenie ();
void Reshenie2 ();
};
void main ()
{setlocale(LC_ALL,"rus");
Spisok As;
p:As.Vvod_Ves();
goto p;
}
int Spisok::Pusto_Q (int *Q) //Дейкстра
{
for (int i=5;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];
// -----------------------------------------------------
// Нахождение кратчайшего пути из 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;
}
if(D[T]!=1000)
{
cout <<"Длина пути: "<< D[T] << " ";
cout << endl;
//Вывод кратчайшего пути на экран дисплея.
cout << "Кратчайший путь: ";
UkZv = Stack;
while ( UkZv != NULL )
{ cout << UkZv->Element+1 << " ";
UkZv = UkZv->Sled;
}
cout << endl;
}
if(D[T]==1000)
{
cout <<"Нет пути!\n";
}
}
void Spisok::Reshenie2 ()//Дейкстра
{ setlocale(LC_ALL,"rus");
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 не пусто.
//for (i=0;i<MaxNodes;i++) //Пока 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];
}
}
// -----------------------------------------------------
// Нахождение кратчайшего пути из 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 <<"Длина пути: "<< D[T] << " ";
cout << endl;
//Вывод кратчайшего пути на экран дисплея.
cout << "Кратчайший путь: ";
UkZv = Stack;
while ( UkZv != NULL )
{ cout << (UkZv->Element+1) << " ";
UkZv = UkZv->Sled;
//UkZv->Element=0;
}
cout << endl;
}
void Spisok::Vvod_Ves()
//Ввод матрицы весов дуг заданного графа.
{setlocale(LC_ALL,"rus");
int k;
int h=0;
ifstream input_file1("1.txt");
cout << "---------------------------------------\n";
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;
if ( A[i][j]<0 ) {h=10;}
k=h;
}
cout<<endl;
}
if(k>5)
{
cout << "Беллмана-Мура: \n";
Reshenie();
}
else
{
cout << "Дейкстры: \n";
Reshenie2();
}
}
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; }
}