Алгоритм на графе

[matan]

Подскажите пожалуйста какой алгоритм используется в этой программе:

ports[N][N]={... };//матрица расстояний
int s;                    //начало пути              
int g;                   //конец пути
int x[N];              //Массив, содержащий единицы и нули для каждой вершины,
                          // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                          // x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[N];               //t[i] - длина кратчайшего пути от вершины s в i
int h[N];              //h[i] - вершина, предшествующая i-й вершине
                // на кратчайшем пути
int u;         
   for (u=0;u<N;u++)
   {
     t[u]=99999999;        //в начале   длина кратчайшего пути от вершины s в u бесконечность
    x[u]=0;        // и нет кратчайшего пути ни для одной вершины

   }
 h[s]=0; 
 t[s]=0;
 x[s]=1; 
 int v=s;
  while(1)                         // Перебираем все вершины, смежные v, и ищем для них кратчайший путь

   {
      
      for(u=0;u<N;u++)
      {
         if(ports[v][u]==0)continue;                           // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+ports[v][u]) 
         {
            t[u]=t[v]+ports[v][u];                                //запоминаем более короткую длину пути в
                                                                //массив t и

            h[u]=v;                                                //запоминаем, что v->u часть кратчайшего 
                                                               //пути из s->u

         }
      }

        // Ищем из всех длин некратчайших путей самый короткий

      int w=99999999;  
      v=-1;                                      // В конце поиска v - вершина, в которую будет 
                                                     // найден новый кратчайший путь. Она станет 
                                                     // текущей вершиной

      for(u=0;u<N;u++)
     {
         if(x[u]==0 && t[u]<w)                         // Если для вершины не найден кратчайший 
                                                                 // путь и если длина пути в вершину u меньше
                                                                 // уже найденной, то
         {
            v=u;                                              // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
          if(v==g)                                              //найден кратчайший путь,     
      {                                                              // выводим его
         printf("Korotkiy put from %d to %d\n",s,g);
         u=g;
         while(u!=s)
         {
            printf(" %d\n",u);
            u=h[u];
         }
         printf(" %d dlina puti - %d\n",s,t[g]);                   //ввыод длины пути
         break;
      }
      x[v]=1;
   }

}
 

Заранее спасибо!

[Igor Borovikov]

Это алгоритм Дейкстры (Dijkstra's Algorithm).

[matan]

Обьясните пожалуйста, что делают эти два цикла

 
for(u=0;u<N;u++) 
      { 
         if(ports[v][u]==0)continue;                           // Вершины u и v несмежные 
         if(x[u]==0 && t[u]>t[v]+ports[v][u]) 
         { 
            t[u]=t[v]+ports[v][u];                                //запоминаем более короткую длину пути в 
                                                                //массив t и 

            h[u]=v;                                                //запоминаем, что v->u часть кратчайшего 
                                                               //пути из s->u 

         } 
      }
 int w=99999999;  
      v=-1;                                      // В конце поиска v - вершина, в которую будет 
                                                     // найден новый кратчайший путь. Она станет 
                                                     // текущей вершиной 

  for(u=0;u<N;u++) 
     { 
         if(x[u]==0 && t[u]<w)                         // Если для вершины не найден кратчайший 
                                                                 // путь и если длина пути в вершину u меньше 
                                                                 // уже найденной, то 
         { 
            v=u;                                              // текущей вершиной становится u-я вершина 
            w=t[u]; 
         } 
      }

[Igor Borovikov]

Подробное описание алгоритма Дейкстры есть на википедии (и на русском, и на английском). Причем в русском варианте есть подробно разобраный пример. А в английском варинате приведена очень полезная метафора, объясняющая алгоритм в наглядных бытовых терминах. Очень рекомендую. Также хорошо пересказать как там написано мне будет трудно

[matan]

Спасибо

[Nerazumovskiy]

кстати вопрос:
Почему люди используют числа типа 9999999 вместо -1 например?

[Yuri Gendelman]

Nerazumovskiy писал(а):

кстати вопрос:
Почему люди используют числа типа 9999999 вместо -1 например?

Я ни разу не слышал про людей, которые используют 9999999 вместо -1.

Иногда 9999999 используют вместо $+\infty$ как начальное значение при поиске минимума. Это допустимо, если известно, что все числа - меньше. Хотя лучше бы так не делать.