Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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

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

Помогите, пожалуйста, уважаемые программисты!
Нужно реализовать алгоритм Данцига - поиска кратчайших путей в графе.
Делал как объясняется тут : 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 в 04:19.
alexboliam вне форума   Ответить с цитированием
Старый 16.05.2018, 22:19   #2
alexboliam
Пользователь
 
Регистрация: 10.10.2017
Сообщений: 37
Репутация: 10
По умолчанию

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


23:33.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru