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

помогите, срочно(((неправильно ищет путь - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Считать текст из файла и вывести на экран сначала вопросительные, а потом восклицательные предложения http://www.cyberforum.ru/cpp-beginners/thread411902.html
доброго времени суток) оч нужна помощь в составление программы!я с++ плохо понимаю(скорее всего вообще не понимаю)=) помогите пожалуйста написать прогу!!!оч нужно задание: Написать...
C++ Работа с консолью На экран выводится файл, который можно листать вперед или назад. По выведенному на экран тексту можно перемещать курсор, который при подводе к символу выделяет его цветом. При нажатии на заданные... http://www.cyberforum.ru/cpp-beginners/thread411900.html
Помогите исправить ошибку C++
Программа должна посчитать р используя s. После ввода любого значения у выдает :"Floating poin eror: Divide by 0. Abnormal program termination." В чем проблема и как её исправить? #include...
Задача на строки C++
вводится строка слов разделенных пробелами(возможны лишние пробелы в начале и в конце строки и между словами). Сформировать строку в которой удалены лишние пробелы и повторявшиеся ранее слова порядок...
C++ Сортировка фамилий по алфавиту http://www.cyberforum.ru/cpp-beginners/thread411894.html
В исходном файле input.txt дано несколько фамилий. Нужно отсортировать их по алфавиту и вставить в файл output.txt. Содержимое input.txt и output.txt вывести на экран. Язык C.
C++ Как реализовать поиск минимального и максимального элемента в двух объектах класса сразу?? Т.е. один минимальный на два объекта, объекты - одномерные массивы подробнее

Показать сообщение отдельно
Stas12
0 / 0 / 0
Регистрация: 20.10.2011
Сообщений: 102

помогите, срочно(((неправильно ищет путь - C++

19.12.2011, 20:45. Просмотров 234. Ответов 0
Метки (Все метки)

вот прога, она неправильно выводит путь по алгоритму дейкстры

#include<iostream>
#include<fstream>
#include<conio.h>
#include<locale.h>
#include<iomanip>

using namespace std;

int min(int *a); // прототип функции
int **Graf; // объявляем матрицу смежности
int *Label; // объявляем массив меток
int *Active; // объявляем массив
int *pred;//вставка 1
int i,j,k;
int Start, N, M, V, Last;

int main()
{
setlocale(LC_ALL, "Russian");
ifstream input("graf.txt");
input>>N>>M>>Start>>Last;
Graf= new int * [N];
for(i=0;i<N;i++)
{
Graf[i]= new int [N];
}
for(i=0;i<N;i++)
for(j=0;j<N;j++)
Graf[i][j]=0;
for(k=0;k<M;k++)
{
input>>i>>j>>V;
Graf[i][j]=V;
Graf[j][i]=V;
}
cout<<"Матрица смежности(весов):"<<endl;
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
cout<<setw(3)<<Graf[i][j];
cout<<"\n";
}
Label= new int [N];
Active= new int [N];
pred=new int[N];// вставка 2
for(i=0;i<N;i++)
{
Active[i]=0;
pred[i]=0;//вставка 3
}
for(i=0;i<N;i++)
Label[i]=32767;
Active[Start]=1;
Label[Start]=0;
i=Start;
cout<<"\nМассив меток:"<<endl;
for(j=0; j<N; j++ )
cout<<Label[j]<<" ";
cout<<"\nМассив пройденных вершин:"<<endl;
for(j=0; j<N; j++ )
cout<<Active[j]<<" ";
do
{
for(j=0;j<N;j++)
if(Graf[i][j]!=0 && Label[j]> Label[i]+ Graf[i][j])
{
Active[j]=1; // помечаем вершину
Label[j]= Label[i]+ Graf[i][j];
pred[j]=i;// вставка 4
cout<<"\nШаг:";
cout<<"\nМассив пройденных вершин:"<<endl;
for(int p=0; p<N; p++)
{
cout<<Active[p]<<" ";
}
cout<<"\nМассив меток:"<<endl;
for(int p=0; p<N; p++ )
cout<<Label[p]<<" ";
cout<<"\n";
}

Active[i]=0;
cout<<"\nШаг:";

cout<<"\nМассив пройденных вершин:"<<endl;
for(int p=0; p<N; p++)
{
cout<<Active[p]<<" ";
}

cout<<"\nМассив меток:"<<endl;
for(int p=0; p<N; p++ )
cout<<Label[p]<<" ";
cout<<"\n";
i=min(Label);
} while(i!=-1);
cout<<"\nМассив пройденных вершин:"<<endl;
for(int p=0; p<N; p++)
{
cout<<Active[p]<<" ";
}
cout<<"\n";
int *Temp;
Temp=new int [N];
j=Last; i=1;
Temp[0]=Last;
while(j!=Start)
{ Temp[i]=pred[j]; i++;j--; }
cout<<"Путь: ";
for(j=i-1;j>=0;j--) cout<<Temp[j]<< " - ";
// вывод результата
cout<<"\nДлина маршрута до "<<Last<<" вершины:"<<Label[Last]<<endl;

getch();
return 0;
}

int min(int *a)
{
int min=32767,k, min_pos=-1;
for(k=0; k<M;k++)
if(a[k]< min && Active[k]==1)
{
min=a[k];
min_pos=k;
}
return min_pos;
}


вот файл graf.txt


6 8 0 5 //количество вершин, количество ребер, стартовая вершина, конечная вершина соответственно
0 1 2
0 4 3
1 2 1
1 3 4
1 4 3
1 5 7
2 5 2
3 4 3

как сделать так , чтобы он правильно выводил путь(т.е. пройденные вершины по порядку)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru