Поиск кратчайщего пути. Опции

[Krjuger]

Здраствуйте,столкнулся с проблемой при реализации поиска кратчайщего пути по алгоритму Дейкстры.
Исходные данные вводятся в виде графа,представленного в форме 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.

[volvo]

Программа вылетает с ошибкой на этапе заполнения вектора

Правильно делает. Ты либо заполняй вектор через push_back, либо сделай dist.reserve(n), чтоб зарезервировать необходимое число элементов, для дальнейшего к ним обращения.

[Krjuger]

В общем я сделал эту программу и на некоторых тестах она выдает правильный результат,но сдать ее компьютеру мне пока что не удалось.
Вот код.

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

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.push_back(INF);       //Сначала все кратчайшие пути из s в i равны бесконечности
      FPath.push_back(0);        // и нет кратчайшего пути ни для одной вершины
      parent.push_back(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)
      {
		  if (start==finish)
              dist[finish]=0;
		  else
			  dist[finish]=-1;
		   break;
      }
      if(v==finish) // Найден кратчайший путь,
      {        
   	   break;
      }
      FPath[v]=1;
   }
 for (int i=0; i<n; i++)
            cout << (dist[i]<INF ? dist[i] : -1) << ' ';
        cout << endl;
 return 0;
}

int 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,n-1,g,n);
	return 0;
}

Полное условие такое.
Для данного графа необходимо вывести список расстояний от первой вершины до всех
остальных. Если от первой вершины до какой-либо другой нет пути, следует вывести -1.
Ввод: граф, представленный в формате FO. Размер графа не более 1000 вершин.
Вывод: последовательность целых чисел .
Примеры:
5
2 0
1 3 0
2 4 0
3 5 0
4 0

Ответ:
0 1 2 3 4

[volvo]

Что-то ты больно много там лишнего делаешь... Вот этот код отрабатывает по крайней мере на приведенном тесте:

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

const int INF = 100*1000*1000;

using namespace std;

void Dejkstra(vector < vector<int> > g, int n, int start)
{
    vector<bool> visited(n, false);

    vector<int> dist(n);
    for(int i = 0; i < n; i++)
    {
        dist[i] = g[start][i];
    }

    int curr, save_start = start;
    for(int i = 0; i < n - 1; i++)
    {
        int min = INF;
        for(int j = 0; j < n; j++)
        {
            if(!visited[j] && (dist[j] < min))
            {
                min = dist[j]; curr = j;
            }
        }
        for(int j = 0; j < n; j++)
            if((dist[j] > dist[curr] + g[curr][j]) && (dist[curr] < INF) && (g[curr][j] < INF))
                dist[j] = dist[curr] + g[curr][j];
        start = curr;
        visited[curr] = true;
    }

    // Ну, поскольку ОТ начальной вершины ДО нее же расстояние - нулевое:
    dist[save_start] = 0;

    // А теперь выводим результаты:
    for(int i = 0; i < n; i++)
    {
        cout << dist[i] << " ";
    }
    cout << endl;
}

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

    vector < vector<int> > g (n, vector<int> (n, INF));

    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);
    }

	Dejkstra(g, n, 0);
	return 0;
}

, и я не вижу причин чтоб он не отработал на остальных.

Только вот не надо опять про правильность ввода данных в матрицу начинать, ладно? Это называется "тебе шашечки, или ехать?" Либо ты заполняешь матрицу, КАК ТОГО ТРЕБУЕТ АЛГОРИТМ, и он работает, либо ты заполняешь матрицу так как хочешь ты, любуешься на нее, а потом, вручную ищешь результат. Не знаю, как тебе, но мне больше нравится второй способ. Тем более, что как бы не была заполнена матрица, при выводе ее можно показать как угодно.

P.S. Если что - я ввод данных вообще не трогал, поправил только инициализацию матрицы.

[Krjuger]

Ну я вроде не настолько туп,чтобы еще привередничать к тому,кто мне помогает.Если у меня в задании есть какие либо извороты,не влияющие на алгоритм решения,то это уже мои личные извороты.Насчет заполнения.Это заполнение идентично тмоу,которое было в прошлой задаче с которой ты мне помог.И та задача сдана,так что сомневаться в правильности ввода не приходится.Кстати а разве мой способ заполнения не удовлетворял условиям алгоритма???Там на выходе получалась матрица смежности и получалась она правильно и не было там никаких ненужных изваротов,которые были в предыдущей задаче.

Большое спасибо,я чуть изменил вывод под свои требования и программа прекрасно работает.