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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
04.01.2014, 15:22     Алгоритм Дейкстры #1
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти ошибку...
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
#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
 
int n,m,a[101][101],s,f,p,h;
bool used[101];
int res[101];
 
int main(){
freopen("input.txt","rt",stdin);
freopen("output.txt","wt",stdout);
memset(a,0,sizeof(a)); 
 
cin >> n >> s >> f;
for (int i=1; i<n+1; i++) res[i]=1000000000;
 
for (int i=1; i<n+1; i++) 
    for (int j=1; j<n+1; j++) {
        cin >> a[i][j];
        if (a[i][j]==-1) a[i][j]=1000000000;
    }
p=s;
memset(used,0,sizeof(used)); used[s]=true; res[p]=0;
for (int k=1; k<n; k++) {
    h=-1;
    for (int j=1; j<n+1; j++)
        if (!used[j] && (h==-1 || res[j]<res[h])) h = j;
    used[h]=true;
    //if (h==1) continue;
    for (int j=1; j<n+1; j++) 
        res[j]=min(res[h]+a[h][j],res[j]);
    p=h;
}
for (int i=1; i<n+1; i++) cout << res[i] << " ";
cout << endl;
 
 
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2014, 15:22     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
04.01.2014, 15:24     Алгоритм Дейкстры #2
http://e-maxx.ru/algo/dijkstra
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
04.01.2014, 15:26  [ТС]     Алгоритм Дейкстры #3
outoftime, знаю, читал... не помогает
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
04.01.2014, 15:32     Алгоритм Дейкстры #4
denysd21012011, P.S. помогать не стану с таким форматированием, ждите пока ответят.

Не по теме:

Код должен быть красивым и читабельным а не просто набором букоффф, можете вообще в хексе писать если вам все равно на форматирование.

ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.01.2014, 16:23     Алгоритм Дейкстры #5
denysd21012011, вам бы не помешало почитать теорию по этому алгоритму, а то у меня такое чувство что вы слабо понимаете что он должен делать, например,
1. строка 34: должна быть проверка на существование ребра p-j, а иначе всё бессмысленно
2. циклы в строках 29-30 и 33-34 вообще должны выполняться в обратном порядке!!!
3. а что если граф не связан?

в общем идите читайте теорию до полного просветления, а вашу текущую программу на помойку
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
04.01.2014, 16:33  [ТС]     Алгоритм Дейкстры #6
ya_noob,
1) Вначале , когда я считываю матрицу, несуществующие ребра я заменяю заведомо большим значением, и это никак не повлияет на алгоритм!

http://e-maxx.ru/algo/dijkstra - здесь как по мне так же все написано... но у меня почему-то не работает
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
04.01.2014, 16:59     Алгоритм Дейкстры #7
Цитата Сообщение от denysd21012011 Посмотреть сообщение
1) Вначале , когда я считываю матрицу, несуществующие ребра я заменяю заведомо большим значением, и это никак не повлияет на алгоритм! http://e-maxx.ru/algo/dijkstra - здесь как по мне так же все написано... но у меня почему-то не работает
если вы внимательно присмотритесь к статье на е-максе, то увидите, что там используются списки смежности, а у вас матрица смежности. будьте внимательнее
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
04.01.2014, 18:42  [ТС]     Алгоритм Дейкстры #8
....

Добавлено через 1 час 19 минут
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
#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
#define mint long long
 
const int INF=1000000000;
mint n,m,a[101][101],s,f,p,h;
bool used[101];
mint res[101];
 
int main(){
freopen("input.txt","rt",stdin);
freopen("output.txt","wt",stdout);
memset(a,0,sizeof(a)); 
 
cin >> n >> s >> f;
for (int i=1; i<n+1; i++) res[i]=INF;
 
for (int i=1; i<n+1; i++) 
   for (int j=1; j<n+1; j++) {
       cin >> a[i][j];
       if (a[i][j]<0) a[i][j]=INF;
   }
 
memset(used,0,sizeof(used)); res[s]=0;
for (int k=0; k<n; k++) {
   h=1;
   for (int j=1; j<n+1; j++)
       if (!used[j] && ((h==s && k!=0) || res[j]<=res[h])) h = j;
   used[h]=true;
   if (res[h]==INF) break;
   for (int j=1; j<n+1; j++) 
       if (a[h][j]!=-1) res[j]=min(res[h]+a[h][j],res[j]);
}
//for (int i=1; i<n+1; i++) cout << res[i] << " ";
if (res[f]==INF) res[f]=-1;
cout << res[f] << endl;
 
 
return 0;
}
Подправил немного, но все равно( 9 из 11 тестов работает)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2014, 07:26     Алгоритм Дейкстры
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.01.2014, 07:26     Алгоритм Дейкстры #9
Цитата Сообщение от denysd21012011 Посмотреть сообщение
Подправил немного, но все равно( 9 из 11 тестов работает)
на будущее: если Вам что-то ясно и очевидно, то подумайте о других: знают ли они о чем знаете Вы?
Условия задачи отсутствует, поэтому можно только догадываться о максимальных значениях n. Может быть слишком маленькие массивы?
9 из 11 тестов работает. Получается что 2 не работают. А что именно выдает на этих тестах: ошибку или превышение времени выполнения?
см комментарии:
Цитата Сообщение от denysd21012011 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
for (int k=0; k<n; k++) {// в этом цикле по задумке нужно сначало найти индекс вершины, которая не помечена и имеет минимальное значение в массиве res[]
  h=1;// изначально индекс этой вершины выбираем равным 1 (но в некоторых случаях вершина с номером 1 может быть уже помечена и иметь минимальное значение res[h] по сравнению с остальными непомечеными). В этих же тестах s имеет значение не равное 1.
  for (int j=1; j<n+1; j++)
    if (!used[j] && ((h==s && k!=0) || res[j]<=res[h])) h = j;
  used[h]=true;// в результате здесь h может остаться равным 1. И перебор ниже мы повторим (уже его делали когда первый раз пометили вершину с индексом 1). И будем повторять этот же перебор пока k не станет равным n.    А нужных вычислений так и не сделаем.
  if (res[h]==INF) break;
  for (int j=1; j<n+1; j++) 
    if (a[h][j]!=-1) res[j]=min(res[h]+a[h][j],res[j]);
}
поэтому переделайте алгоритм выбора непомеченой вершины с минимальным значением в res[].
Yandex
Объявления
05.01.2014, 07:26     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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