//Нахождение расстояния от источника до всех вершин в графе
//с неотрицательными весами (метод Дейкстры).
//Нахождение кратчайшего пути из S в T.
#include <iostream.h>
#define MaxNodes 7
#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 main ()
{
  Spisok A;
  A.Vvod_Ves();
  A.Reshenie();
}

int Spisok::Pusto_Q (int *Q)
{
  for (int i=0;i<MaxNodes;i++)
    if ( *(Q+i)!=0 ) return 0; //Ложь - не пусто!
  return 1; //Истина - пусто!
}

void Spisok::Reshenie ()
{
  int S; // Начальная вершина пути (источник).
  int T; // Конечная вершина пути.
  int u,v,Min;
  int i,j,k;
  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()
//Ввод матрицы весов дуг заданного графа.
{
  cout << "Вводите элементы матрицы весов дуг по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
   for (int j=0;j<MaxNodes;j++)
     {
       cout << "Введите A[" << (i+1) << "," << (j+1) << "]: "; 
       cin >> A[i][j];
       if ( A[i][j]==0 ) A[i][j] = B;
     }
}

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.
{
  svqz q;

  if ( *stk == NULL ) cout<<"Попытка выбора из пустого стека!\n";
  else
	{ *Klad = (**stk).Element;
	  q = *stk; *stk = (**stk).Sled; delete q; }
}

  Вычислить кратчайшее растояние между вершинами s и t в сети[1]:
   (s,a,4), (s,d,6), (a,d,-3), (a,b,8),  (b,t,2), (a,e,5),
   (d,e,2), (e,c,3), (d,c,11), (c,b,-4), (c,t,7), (b,d,-6).

   (s,1), (a,2), (d,3), (b,4), (c,5), (e,6), (t,7),

    0  4  6  0  0  0  0 
    0  0 -3  8  0  5  0
    0  0  0  0 11  2  0
    0  0 -6  0  0  0  2
    0  0  0 -4  0  0  7
    0  0  0  0  3  0  0
    0  0  0  0  0  0  0

   Введите источник: 1
   Матрица расстояний:
   0 4 1 2 6 3 4
   Введите конечную вершину пути: 7
   Кратчайший путь: 1 2 3 6 5 4 7

   путь 1-2-3-6-5-4-7                 с длиной 4,
   путь 1-2-3-6-5-4-3-6-5-4-7         с длиной -1,
   путь 1-2-3-6-5-4-3-6-5-4-3-6-5-4-7 с длиной -6 и т.д.