Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
#1

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

04.01.2014, 15:22. Просмотров 1527. Ответов 8
Метки нет (Все метки)

Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2014, 15:22
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Дейкстры (C++):

Алгоритм Дейкстры
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все...

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

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

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

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

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

8
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
04.01.2014, 15:24 #2
http://e-maxx.ru/algo/dijkstra
0
denysd21012011
3 / 3 / 2
Регистрация: 29.03.2013
Сообщений: 133
04.01.2014, 15:26  [ТС] #3
outoftime, знаю, читал... не помогает
0
outoftime
║XLR8║
756 / 656 / 211
Регистрация: 25.07.2009
Сообщений: 3,289
Записей в блоге: 5
04.01.2014, 15:32 #4
denysd21012011, P.S. помогать не стану с таким форматированием, ждите пока ответят.

Не по теме:

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

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

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

http://e-maxx.ru/algo/dijkstra - здесь как по мне так же все написано... но у меня почему-то не работает
0
ya_noob
_
314 / 148 / 27
Регистрация: 08.10.2011
Сообщений: 432
04.01.2014, 16:59 #7
Цитата Сообщение от denysd21012011 Посмотреть сообщение
1) Вначале , когда я считываю матрицу, несуществующие ребра я заменяю заведомо большим значением, и это никак не повлияет на алгоритм! http://e-maxx.ru/algo/dijkstra - здесь как по мне так же все написано... но у меня почему-то не работает
если вы внимательно присмотритесь к статье на е-максе, то увидите, что там используются списки смежности, а у вас матрица смежности. будьте внимательнее
0
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 тестов работает)
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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[].
0
05.01.2014, 07:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2014, 07:26
Привет! Вот еще темы с решениями:

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

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

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

Алгоритм Дейкстры
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а...


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

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

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