// Алгоритм Дейкстра

#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <iostream>
#define numtop 6    //Число вершин в графе
int v;
using namespace std;
int main ()
{
     setlocale(LC_ALL, "russian");
     int top1 = 0,     // Для ввода вершин
         top2 = 0,    // Для ввода вершин
   toptop = 0;
     cout<<"количество вершин графа >: 6\n";
     int **Matrix = new int*[numtop];
     for (int i = 0 ; i < numtop ; i++)  
         Matrix[i] = new int[numtop];
     for (int i=0; i<numtop; i++)
     {
         for (int j=0; j<numtop; j++)
             Matrix[i][j]=0;    
     }
     cout<<"Введите список ребер: \n";
     cout<<"Для прекращения ввода на очередной запрос введите несуществующие вершины \n";
     while (1)
     {
         cout<<"ИЗ  ";
   cin>>top1;
   cout<<"В  ";
   cin>>top2;
   cout<<"РАССТОЯНИЕ  ";
         cin>>toptop;
         if (top1<numtop && top2<numtop)
         {
             Matrix[top1][top2]=toptop;
             Matrix[top2][top1]=toptop;
         }
         else  
             break;
     }
     //    Вывод на экран матрицы смежности  
     cout<<"\nМатрица смежности:\n";
     for (int i=0; i<numtop; i++)  
     {
         for (int j=0; j<numtop; j++)
             printf ("%2d", Matrix[i][j]);
         cout<<"\n";
     }
int infinity=1000;                     // Бесконечность
    int p=numtop;
    int s;                 
    int g;                 
    cout<<"Введите начальную вершину: ";    
    cin>>s;
    cout<<"Введите конечную вершину: ";
    cin>>g;
    int x[numtop]; //Массив, содержащий единицы и нули для каждой вершины,
                   // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                   // x[i]=1 - кратчайший путь в i-ю вершину уже найден
    int t[numtop];  //t[i] - длина кратчайшего пути от вершины s в i
    int h[numtop];  //h[i] - вершина, предшествующая i-й вершине
               // на кратчайшем пути
    // Инициализируем начальные значения массивов
    int u;      // Счетчик вершин
    for (u=0;u<p;u++)
    {
       t[u]=infinity; //Сначала все кратчайшие пути из s в i  
  //равны бесконечности
       x[u]=0;        // и нет кратчайшего пути ни для одной вершины
    }
    h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
    t[s]=0; // Кратчайший путь из s в s равен 0
    x[s]=1; // Для вершины s найден кратчайший путь
    v=s;    // Делаем s текущей вершиной
     
    while(1)
    {
       // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
       for(u=0;u<p;u++)
       {
          if(Matrix[v][u]==0)continue; // Вершины u и v несмежные
          if(x[u]==0 && t[u]>t[v]+Matrix[v][u]) //Если для вершины u еще не  
  //найден кратчайший путь
              // и новый путь в u короче чем  
  //старый, то
          {
             t[u]=t[v]+Matrix[v][u];    //запоминаем более короткую длину пути в
  //массив t и
             h[u]=v;    //запоминаем, что v->u часть кратчайшего  
  //пути из s->u
          }
       }
       // Ищем из всех длин некратчайших путей самый короткий
       int w=infinity;  // Для поиска самого короткого пути
       v=-1;            // В конце поиска v - вершина, в которую будет  
                        // найден новый кратчайший путь. Она станет  
                        // текущей вершиной
       for(u=0;u<p;u++) // Перебираем все вершины.
       {
          if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший  
                    // путь и если длина пути в вершину u меньше
                    // уже найденной, то
          {
             v=u; // текущей вершиной становится u-я вершина
             w=t[u];
          }
       }
       if(v==-1)
       {
          cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
          break;
       }
       if(v==g) // Найден кратчайший путь,
       {        // выводим его
          cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
        u=g;
        while(u!=s)
          {
             cout<<" "<<u;
             u=h[u];
          }
          cout<<" "<<s<<". Длина пути - "<<t[g];
        break;
       }
       x[v]=1;
    }
    getch();
     getch ();
     return 0;
}