//Нахождение расстояния от источника до всех вершин
//(метод Форда-Беллмана).
//Нахождение кратчайшего пути из 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);
  public:
         Spisok() {Stack = NULL;}
         void Vvod_Ves();
         void Reshenie ();
};

void main ()
{
  Spisok A;
  A.Vvod_Ves();
  A.Reshenie();
}

void Spisok::Reshenie ()
{
  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 << " "; 
     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 в сети:
   (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: 0 4 -4 2 1 -2 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 и т.д.