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

Алгоритм Дейкстры неправильно выводит путь - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Поиск самого длинного слова в строке http://www.cyberforum.ru/cpp-beginners/thread410478.html
Помогите решить задачу!!! Дана строка: Ваша фамилия, имя и отчество записаны через 1 пробел. Найти что длиннее: имя или фамилия. Заранее спасибо!:)
C++ Вывести на экран красным цветом ту строку, где наименьшее число пробелов не знаю как делать с цветами((...а задача: вывести на экран красным цветом ту строку, где наименьшее число пробелов. помогите, пожалуйста. http://www.cyberforum.ru/cpp-beginners/thread410467.html
C++ Рекурсия в нахождении числа ряда Фибоначчи.
Лаба: написать программу, находящуую заданный элемент ряда Фибоначчи. Написал: #include <stdio.h> void main() { int M, i, n; printf("Программа подсчитывает значение требуемого элемента...
C++ хеширование
подкиньте литературы или статей по минимальному совершенному хешированию, алгоритм, производительность, применение. буду очень благодарен
C++ Структуры (С записью в файл) http://www.cyberforum.ru/cpp-beginners/thread410437.html
Вот написал код програмки: условие таково, мы вводим в ручную очки по матчам(игра в футбол),собственно говоря програмка подсчитывает команды которые заняли 1-ые места и команды занявшие 3 места,после...
C++ Структуры данных: списки Для каждого файла в каталоге содержатся следующие сведения: • Имя файла; • Дата создания; • Количество обращений к файлу. Составить программу, которая обепечивает: • Начальное... подробнее

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

Алгоритм Дейкстры неправильно выводит путь - C++

18.12.2011, 14:29. Просмотров 898. Ответов 2
Метки (Все метки)

вот прога, но она неправильно выводит путь(((
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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