Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Граф  (Прочитано 9185 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Денис
Гость
« : 10-12-2007 18:04 » 

помогите исправить прогу на С++  чтобы она выаодилв на экран самый короткий путь. одным числом:
Код:
//Алгоритм Дейкстры.поиска кратчайшего пути
#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();
}

СПАСИБО
« Последнее редактирование: 10-12-2007 18:09 от Алексей1153++ » Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 10-12-2007 18:10 » 

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

Денис
Гость
« Ответ #2 : 10-12-2007 18:19 » 

понял... но помогите))) Улыбаюсь
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 10-12-2007 18:51 » 

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

Денис
Гость
« Ответ #4 : 10-12-2007 18:58 » 

она не правильно выдает ответы... и еше нужно одно число не два... Да-да
спасибо большое!!!))) Хоть один умный человек нашелся))))
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 10-12-2007 19:18 » 

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

расскажи вот что
Код:
  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
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 10-12-2007 19:38 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 10-12-2007 19:45 » 

Sla, учебник не надо, пусть он и расскажет Улыбаюсь
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #8 : 10-12-2007 20:35 » 

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


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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Денис
Гость
« Ответ #9 : 11-12-2007 21:40 » 

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

да я сам ее писал))
Записан
Денис
Гость
« Ответ #10 : 11-12-2007 21:43 » 

народ помогите!!! а что препад прибьет меня... а я хочу жить)))
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 12-12-2007 10:31 » 

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Денис
Гость
« Ответ #12 : 12-12-2007 18:24 » 

СПАСИБО!!! НО ГДЕ ошибка в проге???
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #13 : 12-12-2007 19:02 » 

Денис, во первых, обрати внимание на этот момент, всё ли тут правильно ?
Код:
   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--; //

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

Денис
Гость
« Ответ #14 : 15-12-2007 21:29 » 

не работает))
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines