IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

> Поиск кратчайщего пути.
Krjuger
сообщение 8.11.2010 14:23
Сообщение #1


Профи
****

Группа: Пользователи
Сообщений: 652
Пол: Мужской
Реальное имя: Алексей

Репутация: -  20  +


Здраствуйте,столкнулся с проблемой при реализации поиска кратчайщего пути по алгоритму Дейкстры.
Исходные данные вводятся в виде графа,представленного в форме FO.

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

const int INF = 100*1000*1000;

using namespace std;

int v;
int n;
int Dejstra (int start, int finish, vector < vector<int> > g, int n)
{
   vector < vector<int> > a (n, vector<int> (n));
                        // Будем искать путь из вершины start в вершину finish
    vector<bool> FPath; //Массив, содержащий единицы и нули для каждой вершины,
                        // FPath[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                        // FPath[i]=1 - кратчайший путь в i-ю вершину уже найден
   vector<int> dist;    //dist[i] - длина кратчайшего пути от вершины s в i
   vector<int> parent;  //parent[i] - вершина, предшествующая i-й вершине
   		                // на кратчайшем пути

   // Инициализируем начальные значения массивов
   int u;	// Счетчик вершин
   a=g;
   for (u=0;u<n;u++)
   {
      dist[u]=INF;       //Сначала все кратчайшие пути из s в i равны бесконечности
      FPath[u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   parent[start]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   dist[start]=0; // Кратчайший путь из s в s равен 0
   FPath[start]=1; // Для вершины s найден кратчайший путь
   v=start;    // Делаем start текущей вершиной
   
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<n;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(FPath[u]==0 && dist[u]>dist[v]+a[v][u]) //Если для вершины u еще не 
	                                                //найден кратчайший путь
                                                  	// и новый путь в u короче чем 
                                                	//старый, то
         {
            dist[u]=dist[v]+a[v][u];	//запоминаем более короткую длину пути в
                                     	//массив t и
            parent[u]=v;	            //запоминаем, что v->u часть кратчайшего 
	                                    //пути из s->u
         }
      }

      // Ищем из всех длин некратчайших путей самый короткий
      int w=INF;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет 
                       // найден новый кратчайший путь. Она станет 
                       // текущей вершиной
      for(u=0;u<n;u++) // Перебираем все вершины.
      {
         if(FPath[u]==0 && dist[u]<w) // Если для вершины не найден кратчайший 
                                      // путь и если длина пути в вершину u меньше
                                      // уже найденной, то
         {
            v=u; // текущей вершиной становится u-я вершина
            w=dist[u];
         }
      }
      if(v==-1)
      {
         cout<< -1;
         break;
      }
      if(v==finish) // Найден кратчайший путь,
      {        // выводим его
         cout<< dist[finish];
   	   break;
      }
      FPath[v]=1;
   }
 return 0;
}

void main()
{
    // считываем матрицу графа
    int n;
    int t;
    cin >> n;

    vector < vector<int> > g (n, vector<int> (n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
        if (i == j )
                g[i][j] = 0 ;
        }

    for (int i=0; i<n; i++)
    {
        do
        {
            int pos_t;
            cin >> t;
            pos_t=1;
            if(t)
            {
                g[i][t-1] = 1;
            }
            else
            {
	if (pos_t==1)
	    g[i][i] = 0;
             }
         pos_t++;
        }
        while (t!=0);
	}
	Dejstra (0,4,g,n);
}


Программа вылетает с ошибкой на этапе заполнения вектора кратчайших путей максимальными значениями (dist[u]=INF; )
Компилятор MVS2008.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 28.07.2025 20:26
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"