Граф

[Денис]

помогите исправить прогу на С++  чтобы она выаодилв на экран самый короткий путь. одным числом:

Код:

//Алгоритм Дейкстры.поиска кратчайшего пути
#include <iostream.h>
#include <conio.h>

#define VERTEXES 6	//Число вершин в графе

int v;
int main(int argc, char* argv[])
{
   clrscr();
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;				// Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
     	                         0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };

   // Будем искать путь из вершины s в вершину g
   int s;              		// Номер исходной вершины
   int g;              		// Номер конечной вершины
   cout<<"Введите s: ";  	// Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //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(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не 
	//найден кратчайший путь
            	// и новый путь в u короче чем 
	//старый, то
         {
            t[u]=t[v]+a[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();
}

СПАСИБО

[Алексей++]

не забывай оборачивать код тегом [code]...[/code] , а то включается не нужное форматирование

[Денис]

понял... но помогите)))

[Алексей++]

Денис, а где конкретно помогать ? )) Скажи, ЧТО не так работает , а то я вот щас занят, копаться в коде не могу

[Денис]

она не правильно выдает ответы... и еше нужно одно число не два...
спасибо большое!!!))) Хоть один умный человек нашелся))))

[Алексей++]

Денис, рано радуешься )  Твой ответ мне ничего не даёт...

расскажи вот что

Код:

  int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
     	                         0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };

 - я не знаю, что значит матрица смежности графа

[Sla]

Это называется "критический путь" - Учебник назвать? номер страницы? параграф?

[Алексей++]

Sla, учебник не надо, пусть он и расскажет

[RXL]

Была уже тема про графы.
https://forum.shelek.ru/index.php/topic,7037.0.html


Денис, программу сам писал?

[Денис]

матрища эта описывает сам граф...

да я сам ее писал))

[Денис]

народ помогите!!! а что препад прибьет меня... а я хочу жить)))

[Sla]

почитай тут http://alexvd.3dnews.ru/index.php?go=Page&id=22

[Денис]

СПАСИБО!!! НО ГДЕ ошибка в проге???

[Алексей++]

Денис, во первых, обрати внимание на этот момент, всё ли тут правильно ?

Код:

   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // Кратчайший путь из s в s равен 0
   x[s]=1; // Для вершины s найден кратчайший путь

какой у тебя индекс - ZeroBased или нет ?

может так надо (отнять единицы от s и g)

Код:

   int s=2;              		// Номер исходной вершины
   int g=5;              		// Номер конечной вершины
   cout<<"Введите s: ";  	// Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;

s--; //
g--; //

а ещё проконтролировать границы надо

[Денис]

не работает))