Правила форума
Внимание!
Исходные данные вводятся в виде графа,представленного в форме 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.
