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

> Внимание!

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

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

> Поиск кратчайщего пути.
сообщение
Сообщение #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

 





- Текстовая версия 25.04.2024 8:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name