Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.65
AnDrew_LP
161 / 161 / 42
Регистрация: 29.05.2010
Сообщений: 435
#1

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

15.01.2011, 19:55. Просмотров 3871. Ответов 14
Метки нет (Все метки)

Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет.
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

http://www.cyberforum.ru/cpp-beginners/thread630873.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2011, 19:55
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Дейкстры (C++):

Алгоритм Дейкстры
Всем добрый день,уважаемые программисты! Помогите пожалуйста решить вот эту...

Алгоритм Дейкстры
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5...

Алгоритм Дейкстры С++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление...

Алгоритм Дейкстры
Пытаюсь сейчас его понять, как я понял сперва надо оставить матрицу смежности,...

Алгоритм Дейкстры
Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной...

14
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 20:14 #2
AnDrew_LP, условия посмотри как пишешь, че еще за запятая в if () ? Oo
и не понимаю зачем старт и финиш. Для алгоритра Дейкстры это не надо
0
AnDrew_LP
161 / 161 / 42
Регистрация: 29.05.2010
Сообщений: 435
15.01.2011, 20:29  [ТС] #3
я в с++ новичек,мало чего знаю.
Как перечислять несколько условий?
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 20:45 #4
AnDrew_LP, && - и
|| - или
^ - xor

Добавлено через 1 минуту
AnDrew_LP, объясни как работает функция find_minimum, чет не врубаюсь пока
1
AnDrew_LP
161 / 161 / 42
Регистрация: 29.05.2010
Сообщений: 435
15.01.2011, 20:49  [ТС] #5
так:if(условие1)&&(условие2) или так: if(условие1&&условие2)?
на счет find_minimum:
сначала минимуму присваевается любая не использованая точка.
затем поиск наименьшей метки.
Я на Паскале сначала эту прогу написал, затем попробовал на с++.На Паскале все работает.
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 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, кинь тогда еще паскалевский код посмотреть. Разберемся ща что не так
1
AnDrew_LP
161 / 161 / 42
Регистрация: 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.
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 22:20 #8
AnDrew_LP, В коде который выложили:
- в строках 25 и 31 замените запятые на &&
- строку 54 уберите совсем.
И должно заработать.
1
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 22:31 #9
valeriikozlov, вы проверяли? у меня как-то не очень заработало с найденным мной вручную геодезическим деревом не сходится(
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 22:38 #10
Цитата Сообщение от sandye51 Посмотреть сообщение
у меня как-то не очень заработало
какой у Вас результат в ручную получился и каким путем?
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 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
алгоритмом крускала не проверял
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
15.01.2011, 22:54 #12
Цитата Сообщение от sandye51 Посмотреть сообщение
расстояния (1 -10)
0 3 4 2 5 10 11 5 19 17
Ну вообще-то точно такие результаты программа и выдает.
1
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
15.01.2011, 23:01 #13
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Ну вообще-то точно такие результаты программа и выдает.
действительно, чет я не то исправил видать)
0
AnDrew_LP
161 / 161 / 42
Регистрация: 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();
  }
0
sandye51
программист С++
833 / 592 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
16.01.2011, 13:50 #15
AnDrew_LP, можн просто нажать ctrl+alt+f7 и заново перестроит решение
1
16.01.2011, 13:50
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2011, 13:50
Привет! Вот еще темы с решениями:

Алгоритм Дейкстры
Написал программу, проверил код, в MVS6 С++ компилируется без ошибок. Но вот не...

Алгоритм Дейкстры
Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше...

Алгоритм Дейкстры
Ребятушки, помогите, пожалуйста. Нужна реализация алгоритма дейкстры на...

Алгоритм Дейкстры
Здравствуйте!!! Есть код для нахождения длин от начальной вершины до всех...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru