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

С++ для начинающих

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

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

04.01.2014, 15:22. Просмотров 1318. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2014, 15:22     Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include&lt;iostream&gt; #include&lt;fstream&gt; ...

Алгоритм Дейкстры (цена на бензин) - C++
Думаю с этой задачей многие сталкивались :) Входные данные Во входном файле INPUT.TXT записано сначала число N (1 ≤ N ≤ 100), затем...

Работа с графами. Алгоритм Дейкстры - C++
Может у кого есть исходник для реализации алгоритма Дейкстры, когда граф представлен не матрицей смежности, а списком рёбёр. Просто есть...

Вставить алгоритм Дейкстры в программу - C++
Вот рабочая программа которая находит кратчайшый путь по алгоритму Дейкстры А вот моя в которую нужно вставить алгоритм ...

Вывод пути (алгоритм Дейкстры) - C++
Реализация алгоритма Дейкстра. В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о...

Алгоритм Дейкстры с рандомной матрицей - C++
Необходимо, чтобы при запуске программы создавалась рандомная матрица 9x9 в которой: рандом генерируется по всей матрице, кроме главной...

Алгоритм Дейкстры. Консольное приложение - C++
Помогите, помогите, помогите кто чем может, пожалуйста!.. срочно пипец вообще как нужна программа на плюсах, реализующая алгоритм Дейкстры...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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║
508 / 430 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
04.01.2014, 15:32     Алгоритм Дейкстры #4
denysd21012011, P.S. помогать не стану с таким форматированием, ждите пока ответят.

Не по теме:

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

ya_noob
_
201 / 145 / 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
_
201 / 145 / 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++
Лабиринт задается матрицей, где 0 стены, 1 проходы, s - начальная вершина, f - конечная. Лабиринт считывается из файла. Не могу сообразить,...

Алгоритм Дейкстры неправильно выводит путь - C++
вот прога, но она неправильно выводит путь((( #include&lt;iostream&gt; #include&lt;fstream&gt; #include&lt;conio.h&gt; #include&lt;locale.h&gt; ...

Алгоритм Дейкстры в связном списке + файлы. - C++
Задача такова : Имеются n городов. Некоторые из них соединены дорогами известной длины. Найти кратчайшие маршруты из заданного города в...

Алгоритм Дейкстры (часть кода есть) - C++
Здравствуйте! Нужно реализовать на С++ такую консольную программу: 1. Задается массив размерности n; 2. Найти максим. j такой, что a...

Требуется реализовать алгоритм Дейкстры начинающему программисту - C++
Ребята огромная просьба помочь с программой. Условия следушие-реализовать алгоритм Дейкстры на С++. Я сидел парился и смог только часть...


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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 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     Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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