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

Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.65
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
15.01.2011, 19:55     Алгоритм Дейкстры #1
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет.
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
#include<iostream>
#include<fstream>
#include<iomanip>
#include<conio.h>
using namespace std;
 
int start,finish,n;
int ves[20][20],metka[20];
bool used[20];
 
void read_from_file()
 {
  ifstream f("deikstra.txt");
    f >> n >> start>> finish;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       f>>ves[i][j];
 }
int find_minimum()
{
 int min;
 for(int i=1;i<=n;i++)
     if (!used[i]) min=i;
 for(int i=1;i<=n;i++)
     if(!used[i],metka[min]>metka[i]) min=i;
 return min;
}
void find_neighbours(int a)
{
 for(int i=1;i<=n;i++)
  if(ves[a][i]!=0,!used[i],metka[i]>ves[a][i]+metka[a])
   metka[i]=ves[a][i]+metka[a];
 used[a]=true;
}
void otladka()
{
 for(int i=1;i<=n;i++)
  cout<<i<<' '<<metka[i]<<' '<<used[i]<<' ';
 cout<<"\n";
}
bool finish_program()
{
 bool f=true;
 for(int i=1;i<=n;i++)
  if(!used[i]) f=false;
 return f;
}
int main()
  {
   read_from_file();
   for(int i=1;i<=n;i++)
    metka[i]=100;
   metka[start]=0;
   for(int i=1;i<=n;i++)
   while(!finish_program())
   {
    int nowusing=find_minimum();
    find_neighbours(nowusing);
    otladka();
   }
   cout<<metka[finish];
   cin.get();
  }
Файл deikstra.txt:
Pascal
1
2
3
4
5
6
7
8
9
10
11
 10 1 10
0 3 0 2 0 0 0 0 0 0
3 0 0 0 0 0 0 2 0 0
0 0 0 2 1 0 0 0 0 0
2 0 2 0 0 0 0 5 0 0
0 0 1 0 0 5 0 0 0 0
0 0 0 0 5 0 9 0 0 7
0 0 0 0 0 9 0 6 8 0
0 2 0 5 0 0 6 0 0 0
0 0 0 0 0 0 8 0 0 10
0 0 0 0 0 7 0 0 10 0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2011, 19:55     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры С++ C++
C++ Алгоритм Дейкстры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 20:14     Алгоритм Дейкстры #2
AnDrew_LP, условия посмотри как пишешь, че еще за запятая в if () ? Oo
и не понимаю зачем старт и финиш. Для алгоритра Дейкстры это не надо
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
15.01.2011, 20:29  [ТС]     Алгоритм Дейкстры #3
я в с++ новичек,мало чего знаю.
Как перечислять несколько условий?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 20:45     Алгоритм Дейкстры #4
AnDrew_LP, && - и
|| - или
^ - xor

Добавлено через 1 минуту
AnDrew_LP, объясни как работает функция find_minimum, чет не врубаюсь пока
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
15.01.2011, 20:49  [ТС]     Алгоритм Дейкстры #5
так:if(условие1)&&(условие2) или так: if(условие1&&условие2)?
на счет find_minimum:
сначала минимуму присваевается любая не использованая точка.
затем поиск наименьшей метки.
Я на Паскале сначала эту прогу написал, затем попробовал на с++.На Паскале все работает.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 20:53     Алгоритм Дейкстры #6
AnDrew_LP, пример
C++
1
        if(ves[a][i] != 0 && !used[i] && metka[i] > ves[a][i] + metka[a])
второй вариант

Добавлено через 2 минуты
AnDrew_LP, кинь тогда еще паскалевский код посмотреть. Разберемся ща что не так
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
15.01.2011, 20:55  [ТС]     Алгоритм Дейкстры #7
Pascal
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
const maxn=10;
var
 nowusing,i,n,start,finish:byte;
 ves:array[1..maxn,1..maxn] of byte;
 metka:array[1..maxn] of byte;
 used:array[1..maxn] of boolean;
 
procedure read_from_file;
var t:text;
 i,j:byte;
 begin
  assign(t,'deikstra.in');
  reset(t);
  readln(t,n,start,finish);
  for i:=1 to n do
   begin
    for j:=1 to n do
     read(t,ves[i,j]);
    readln(t);
   end;
 end;
 
procedure find_minimum;
var i:byte;
begin
 for i:=1 to n do
  if not used[i] then nowusing:=i;
 for i:=1 to n do
  if (not used[i])and(metka[nowusing]>=metka[i]) then nowusing:=i;
end;
 
procedure find_neighbours(a:byte);
var i:byte;
begin
 for i:=1 to n do
  if(ves[a,i]<>0)and(not used[i])and(metka[i]>ves[a,i]+metka[a])
    then metka[i]:=ves[a,i]+metka[a];
 used[a]:=true;
end;
 
function finish_program:boolean;
var i:byte;
begin
  finish_program:=true;
 for i:=1 to n do
  if not used[i] then finish_program:=false;
end;
 
procedure otladka;
var i:byte;
begin
 writeln(nowusing);
  for i:=1 to n do
   write(metka[i],' ');
  writeln;
  for i:=1 to n do
   write(used[i],' ');
   readln;
end;
 
procedure main;
begin
  for i:=1 to n do
   metka[i]:=255;
 metka[start]:=0;
 repeat
  find_minimum;
  find_neighbours(nowusing);
  {otladka;}
 until finish_program;
end;
 
begin
 read_from_file;
 main;
 writeln(metka[finish]);
 readln;
end.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 22:20     Алгоритм Дейкстры #8
AnDrew_LP, В коде который выложили:
- в строках 25 и 31 замените запятые на &&
- строку 54 уберите совсем.
И должно заработать.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 22:31     Алгоритм Дейкстры #9
valeriikozlov, вы проверяли? у меня как-то не очень заработало с найденным мной вручную геодезическим деревом не сходится(
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 22:38     Алгоритм Дейкстры #10
Цитата Сообщение от sandye51 Посмотреть сообщение
у меня как-то не очень заработало
какой у Вас результат в ручную получился и каким путем?
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 22:49     Алгоритм Дейкстры #11
valeriikozlov, как раз Дейкстра.
корень - 1
расстояния (1 -10)
0 3 4 2 5 10 11 5 19 17
алгоритмом крускала не проверял
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 22:54     Алгоритм Дейкстры #12
Цитата Сообщение от sandye51 Посмотреть сообщение
расстояния (1 -10)
0 3 4 2 5 10 11 5 19 17
Ну вообще-то точно такие результаты программа и выдает.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 23:01     Алгоритм Дейкстры #13
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Ну вообще-то точно такие результаты программа и выдает.
действительно, чет я не то исправил видать)
AnDrew_LP
160 / 162 / 9
Регистрация: 29.05.2010
Сообщений: 435
16.01.2011, 12:42  [ТС]     Алгоритм Дейкстры #14
Спасибо всем,но я уже сам разобрался))не мог найти ошибку, потому что Visual studio вместо того,чтоб заново скомпилировать файл,ипользовало уже скомпилированый.Из-за этого постоянно выводились те же самые результаты.Удалил папку Debug и все заработало)Переделал с указателями,вот то, что получилось в итоге
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
#include<iostream>
#include<fstream>
#include<iomanip>
#include<conio.h>
using namespace std;
 
void read_from_file(int* n,int* start,int*finish,int* ves)
 {
  ifstream f("deikstra.txt");
  if(!f) cout<<"File error!\n";
  else
  {
    f >> *n >> *start>> *finish;
    for(int i=0;i<*n;i++)
      for(int j=0;j<*n;j++)
       f>>*(ves+i*10+j);
  }
 }
int find_minimum(int* n,bool* used,int* metka)
{
 int min;
 for(int i=0;i<*n;i++)
     if (*(used+i)==false) {min=i;break;}
 for(int i=0;i<*n;i++)
     if(*(used+i)==false && *(metka+min)>*(metka+i)) min=i;
 return min;
}
void find_neighbours(int a,int n,int* ves,bool* used,int* metka)
{
 for(int i=0;i<n;i++)
  if(*(ves+a+i*10)!=0 && !*(used+i) && *(metka+i)>*(ves+a+i*10)+*(metka+a))
   *(metka+i)=*(ves+a+i*10)+*(metka+a);
 *(used+a)=true;
}
void otladka(int* n,int* metka,bool* used)
{
 for(int i=0;i<*n;i++)
  cout<<i+1<<':'<<*(metka+i)<<' '<<*(used+i)<<' ';
 cout<<"\n";
}
bool finish_program(int* n,bool* used)
{
 bool f=true;
 for(int i=0;i<*n;i++)
  if(!*(used+i)) f=false;
 return f;
}
int main()
  {
     int start,finish,n;
     int ves[10][10],metka[10];
     bool used[10];
    read_from_file(&n,&start,&finish,&ves[0][0]);
      start--;
      finish--;
    for(int i=0;i<n;i++)
     {metka[i]=100;used[i]=false;}
    metka[start]=0;
   while(!finish_program(&n,&used[0]))
   {
    int nowusing=find_minimum(&n,&(used[0]),&(metka[0]));
    find_neighbours(nowusing,n,&ves[0][0],&used[0],&metka[0]);
    /*otladka(&n,&metka[0],&used[0]);*/
   }
   cout<<metka[finish];
   cin.get();
  }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2011, 13:50     Алгоритм Дейкстры
Еще ссылки по теме:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры

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

Или воспользуйтесь поиском по форуму:
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
16.01.2011, 13:50     Алгоритм Дейкстры #15
AnDrew_LP, можн просто нажать ctrl+alt+f7 и заново перестроит решение
Yandex
Объявления
16.01.2011, 13:50     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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