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

[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]

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

//Алгоритм Дейкстры.поиска кратчайшего пути
#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. Если что - я ввод данных вообще не трогал, поправил только инициализацию матрицы.