Форум программистов, компьютерный форум CyberForum.ru

Не могу понять ошибку. При вводе значений вылетает программа. - C++

Восстановить пароль Регистрация
 
Xalik
Сообщений: n/a
26.11.2011, 01:55     Не могу понять ошибку. При вводе значений вылетает программа. #1
Задача: Дана система 2-х сторонних дорог. Известна цена на каждом пути. Определить убыток при закрытии дороги.

Алгоритм: Функция "poisk" в моей программе находит в графе и выводит самый дешёвый путь (вершины) и его цену. Функция "del" удаляет в матрице инцидентности цену на указанном пути. Исходные данные с файла, где 1 строка кол-во вершин.

Проблема: Прога работает лишь при использовании функции poisk. а всё остальное игнорирует и зависает. Нужна помощь!

Код:
//Поиск самого дешевого пути
#include <iostream>
#include <conio.h>


#define VERTEXES 20 //Число вершин в графе
using namespace std;
int d1,d2;
//---------------------------------------------------------------------------
int poisk(int a[VERTEXES][VERTEXES],int n,int s,int g)
{ int u,v;
int ukst=-1;
int stack[VERTEXES];
int infinity=1000; // Бесконечность
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - самый дешеывй путь в i-ю вершину уже найден
int t[VERTEXES]; //t[i] - длина самого дешевого пути от вершины s в i
int h[VERTEXES]; //h[i] - вершина, предшествующая i-й вершине
// на самом дешевом пути
for (u=0;u<n;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной


/* for (u=0;u<k;u++)
{
cin>>d>>b>>c;
a[d][b]=a[b][d]=c;
};*/

while(1)
{
// Перебираем все вершины, смежные v, и ищем для них самый дешевый путь
for(u=0;u<n;u++)
{


if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не найден самый дешевый путь
// и новый путь в u дешевле чем старый, то

{
t[u]=t[v]+a[v][u]; //запоминаем более дешевую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть самого дешевого
//пути из s->u
}
}

// Ищем из всех длин недешевых путей самый дешевый
int w=infinity; // Для поиска самого дешевого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый самый дешевый путь. Она станет
// текущей вершиной
for(u=0;u<n;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден самый дешевый
// путь и если цена пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
cout<<"HeT nyTu u3 BepwuHbI "<<s<<" B BepwuHy "<<g<<"."<<endl;
break;
}
if(v==g) // Найден самый дешевый путь,
{ // выводим его
cout<<"CaMbIu deweBbIu nyTb u3 BepwuHbI "<<s<<" B BepwuHy "<<g<<" : ";
u=g;
cout<<s<<" ";
while(u!=s)
{
// cout<<" "<<u;
stack[++ukst]=u;
u=h[u];
}
while (ukst>-1) cout<<stack[ukst--]<<" ";// вывод пути

cout<<" . LI,eHa nyTu - "<<t[g];
break;
}
x[v]=1;
} return 0;
}

//---------------------------------------------------------------------------
int del(int a[VERTEXES][VERTEXES])
{

cout<<"\n goroda dl9 ydaleni9: ";
cin>>d1;
cout<<"\n goroda dl9 ydaleni9: ";
cin>>d2;
a[d1][d2]=0;
a[d2][d1]=0;
return 0;
}





int main()
{
// clrscr();

int n= VERTEXES; // Количество вершин в графе
int a[VERTEXES][VERTEXES]={0};


// Будем искать путь из вершины s в вершину g
int s; // Номер исходной вершины
int g,k,d,b,c,d1,d2; // Номер конечной вершины



cout<<"BBeguTe roPod otkyga Ha4uHaeTc9 nyTb: "; // Номер может изменяться от 0 до p-1
cin>>s;
cout<<"BBeguTe ropod rde 3akoH4uTc9 nyTb: ";
cin>>g;



freopen("input.txt","r",stdin);
int i,j; // для чтения из файла
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>a[i][j];


// Инициализируем начальные значения массивов
// Счетчик вершин
poisk(a,n,s,g);
del(a);
poisk(a,n,s,g);

getch();



}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит

Нет пути из вершины 3 в вершину 6.

После ввода s = 0, q = 2 программа выводит

Самый дешевый путь из вершины 0 в вершину 2: 2 5 1 0. Цена пути = 3.*/

Добавлено через 13 минут
я конечно не дописал прогу до конца (нахождение убытка), но это пока не суть, т.к. уже виснет
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2011, 01:55     Не могу понять ошибку. При вводе значений вылетает программа.
Посмотрите здесь:

C++ При вводе букв (переменных)глючит программа,а должно выбивать ошибку
C++ Компилятор выдает ошибку при объявлении массива. Не могу понять где соль
C++ не могу понять ошибку типов переменных при деление идет обращение в ноль
C++ Не могу понять, как исправить ошибку в при вызове методов класса
почему где подчеркнуто выдает ошибку,понять не могу(программа не дописана) C++
Программа на С++ вылетает, не могу понять почему!? C++
Выдает ошибку при компиляции. Не могу понять почему C++
Задание на ряды: программа зацикливается при вводе некоторых значений C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 07:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru