|
0 / 0 / 0
Регистрация: 25.10.2021
Сообщений: 8
|
||||||
Проблема с выводом алгоритма Флойда — Уоршелла03.01.2024, 06:26. Показов 2603. Ответов 12
0
|
||||||
| 03.01.2024, 06:26 | |
|
Ответы с готовыми решениями:
12
Реализация Алгоритма Флойда-Уоршелла Задача коммивояжера с использованием алгоритма Флойда-Уоршелла Алгоритм Флойда-Уоршелла |
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 129
|
|||||||||||||
| 03.01.2024, 12:51 | |||||||||||||
|
Решение:
попробуйте заменить
int - тривиальный тип, его можно копировать через std::memcpy/std::memmove. Не говоря уже о том, что это все можно переписать на std::valarray в 2 строчки. Я бы советовал вам язык подучить, прежде чем лезть в алгоритмы и абстракции, ибо из-за того, что вы вручную делаете столько рутинных операций, ваш код превращается в простыню, и его довольно трудно читать и вам, и другим. Добавлено через 1 час 18 минут И вообще весь код надо бы разделить на две части: Класс матрицы (отвечает за рутину: копирование, создание/удаление) на основе std::valarray.Класс графа. А то у вас в коде куча лишних new и delete в цикле.Это очень сильно бьет по производительности, отдельный класс-обертка над std::valarray это исправит.Добавлено через 3 минуты Если говорить еще проще, ваш класс графа делает то, чем он заниматься не должен. Если сделать все, как я написал, вам будет проще добавлять функционал, в котором алгоритмическая составляющая на первом месте, а значит, выполнять задания.
1
|
|||||||||||||
|
Вездепух
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
|
|||
| 04.01.2024, 07:33 | |||
|
А чего вы ожидали? У вас в исходной матрице смежности много нулей. В результате получается, что практически между любыми двумя вершинам существует путь из нулевых ребер. Ноль - это ведь кратчайший, короче некуда, правда? Вот алгоритм Флойда-Уоршелла радостно и находит такие пути. Для вашей матрицы смежности все нули - это правильный ответ. Почему вас это удивляет? Собственно, вопрос в том, почему у вас в матрице смежности сидят нули? Что они означают? Судя по комментариям в вашем коде, отсутствующие ребра обозначаются через INT_MAX. Ну тогда ноль - это обычное ребро нулевого веса. У вас в матрице никаких INT_MAX нет вообще. То есть граф полный - все ребра без исключения присутствуют и многие из них имеют нулевой вес. Ну так неудивительно, что все кратчайшие пути оказались нулевыми. Так и есть. Это правильный ответ.
1
|
|||
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 129
|
||||||||||||
| 04.01.2024, 08:06 | ||||||||||||
Graph::addEdges:
Но код все равно "попахивает", причем сильно.
0
|
||||||||||||
|
Вездепух
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
|
|||||||
| 04.01.2024, 08:10 | |||||||
Сообщение было отмечено syperdog как решение
РешениеНули там сидели изначально:
main лишь заменяют некоторые из них на "ненули".Исходная матрица выглядит так: Вот они, нулики. P.S. У ТС в функции Graph::printVerticesAndEdges() признаком отсутствия ребра считается 0. А в Graph::floydWarshall() признаком отсутствия ребра считается INT_MAX. Вот из-за этой каши все и проблемы.
1
|
|||||||
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 129
|
|
| 04.01.2024, 08:14 | |
|
0
|
|
|
Вездепух
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
|
|||||||
| 04.01.2024, 08:27 | |||||||
|
Вообще-то вся идея, весь смысл использования огромного guard-значения, вроде INT_MAX, для обозначения отсутствующих ребер как раз и заключается в том, чтобы устранить необходимость делать
std::min, т.е. никакого дополнительного if не нужно (однако следить за переполнениями - нужно).А применить INT_MAX и потом еще все таки возиться с дополнительными if - это уже профанация и непонимание идеи.
1
|
|||||||
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 129
|
|
| 04.01.2024, 08:30 | |
|
TheCalligrapher, еще раз подтверждается моя подпись...
0
|
|
|
6136 / 2830 / 1039
Регистрация: 01.06.2021
Сообщений: 10,324
|
|
| 05.01.2024, 17:14 | |
|
IMHO, если в коде используется INT_MAX или что-нибудь похожее, то это признак плохого качества
0
|
|
|
Заблокирован
|
|
| 06.01.2024, 01:10 | |
|
Плохого качества чего ?
--- Хинт : Использование любого значения из диапазона в качестве контрольного - частая практика.
1
|
|
|
6136 / 2830 / 1039
Регистрация: 01.06.2021
Сообщений: 10,324
|
|
| 06.01.2024, 02:51 | |
|
SmallEvil, плохое качество алгоритма. Только на этом форуме видел много раз, как из-за этих предельных значений возникало много ошибок. Порой, эти значения ошибочно даже участвовали в вычислениях, тогда как они должны были служить для проверок. Иногда из-за них случались переполнения.
0
|
|
|
Вездепух
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
|
|
| 06.01.2024, 04:54 | |
|
В данном случае, конечно же, для того, чтобы использовать большое значение в качестве guard-значения, нужно было либо использовать в этой роли
INT_MAX / 2, либо суммирование и сравнение расстояний выполнять в рамках более широкого типа.А в текущем варианте из-за INT_MAX получилось переполнение, которое принялись лечить через дополнительный if. В результате чего сразу возникает вопрос о том, к чему тут вообще INT_MAX, если для обозначения отсутствующих ребер уже ранее был выбран 0.
1
|
|
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 129
|
|
| 09.01.2024, 16:33 | |
|
TheCalligrapher, согласен с Royal_X. По-моему лучше написать класс
integer, объект которого приводим к целочисленному типу, содержит перегрузки операторов и может быть в состоянии "бесконечности", т.е. integer { infinity } > n всегда false. Туда можно напихать других условных математических значений, для представления которых трюками, подобными этим манипуляциям с INT_MAX не обойтись.И еще, чисто опционально, впихнуть user-defined literal для целочисленных литералов.
0
|
|
| 09.01.2024, 16:33 | |
|
Помогаю со студенческими работами здесь
13
Алгоритм Флойда-Уоршелла Алгоритм Флойда-Уоршелла Алгоритм Флойда — Уоршелла Алгоритм Флойда-Уоршелла Алгоритм Флойда-Уоршелла Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop?
Ниже её машинный перевод.
После долгих разбирательств я наконец-то вернула себе. . .
|
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод
Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод.
Thinkpad X220 Tablet —. . .
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|