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

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

Восстановить пароль Регистрация
 
Stas12
0 / 0 / 0
Регистрация: 20.10.2011
Сообщений: 102
19.12.2011, 20:45     помогите, срочно(((неправильно ищет путь #1
вот прога, она неправильно выводит путь по алгоритму дейкстры

#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

как сделать так , чтобы он правильно выводил путь(т.е. пройденные вершины по порядку)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.12.2011, 20:45     помогите, срочно(((неправильно ищет путь
Посмотрите здесь:

Помогите, пожалуйста, с лабами, срочно!!! C++
Помогите найти ошибки.срочно C++
C++ Срочно Народ помогите!
C++ Помогите пожалуйста (срочно)
Помогите открыть файл через его путь C++
помогите, неправильно выводит путь алгоритм Дейкстры C++

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

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

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