Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.05.2018, 20:54   #1
alexboliam
Пользователь
 
Регистрация: 10.10.2017
Сообщений: 44
По умолчанию Найти ошибку в алгоритме

Помогите, пожалуйста, уважаемые программисты!
Нужно реализовать алгоритм Данцига - поиска кратчайших путей в графе.
Делал как объясняется тут : http://uchimatchast.ru/teory/danceg.php
UPD: При любой матрице и ее размерности, неправильно считает именно значения Arr[3][0] и Arr[3][1] (матрицы в самом низу)
Сделал что-то такое, но ответ выходит частично неправильный:
для матрицы
0 100 -2 100
4 0 3 100
100 100 0 2
100 -1 100 0
(100 - max или бесконечность, т.е. нет дуги напрямую)
Код:
for (int m = 1; m < n; m++) {
        
        for (int k = 0; k < m; k++) {//проходимся по последней строке m
            for (int j = 0; j < m; j++) {
                min = Arr[m][j];
                if (Arr[m][k] + Arr[k][j] < min) {
                    min = Arr[m][k] + Arr[k][j];
                    Arr[m][j] = min;
                }
            }
        }
        for (int k = 0; k < m; k++) {//проходимся по последнему столбцу m
            for (int i = 0; i < m; i++) {
                min1 = Arr[i][m];
                if (Arr[i][k] + Arr[k][m] < min1) {
                    min1 = Arr[i][k] + Arr[k][m];
                    Arr[i][m] = min1;
                }
            }
        }
        for (int i = 0; i < m - 1; i++) {//Метод Флойда для матрицы без последней строки и столбца
            for (int j = 0; j < m - 1; j++) {
                Arr[i][j] = fmin(Arr[i][j], Arr[i][m] + Arr[m][j]);
            }
        }
    }
Выходит так:
0 -1 -2 0
4 0 2 4
max max 0 2
3 -1 1 0

Последний раз редактировалось alexboliam; 17.05.2018 в 03:19.
alexboliam вне форума Ответить с цитированием
Старый 16.05.2018, 21:19   #2
alexboliam
Пользователь
 
Регистрация: 10.10.2017
Сообщений: 44
По умолчанию

UP: При любой матрице и ее размерности, неправильно считает именно значения Arr[3][0] и Arr[3][1]
alexboliam вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Найти седловые точки в матрице(помогите найти ошибку) - pascal tdsotm Помощь студентам 0 20.11.2014 18:57
Помогите найти ошибку - StrToFloat выдаёт ошибку EConvertError для ячеек StringGrid (Delphi) Artsiom Помощь студентам 10 18.12.2013 14:10
Исправить ошибку арифметического переполнения в алгоритме. DarkDen Паскаль, Turbo Pascal, PascalABC.NET 2 11.05.2013 13:16
Не покидает чувство, что я допустил ошибку в алгоритме/коде (Python) nextdrift Python 2 08.03.2013 23:10
Ошибка в алгоритме?Выдает ошибку после компиляции. Aerial Общие вопросы C/C++ 2 12.05.2010 16:52