|
0 / 0 / 0
Регистрация: 25.10.2021
Сообщений: 8
|
||||||
Проблема с выводом алгоритма Флойда — Уоршелла03.01.2024, 06:26. Показов 2616. Ответов 12
0
|
||||||
| 03.01.2024, 06:26 | |
|
Ответы с готовыми решениями:
12
Реализация Алгоритма Флойда-Уоршелла Задача коммивояжера с использованием алгоритма Флойда-Уоршелла Алгоритм Флойда-Уоршелла |
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
|
|||||||||||||
| 03.01.2024, 12:51 | |||||||||||||
|
Решение:
попробуйте заменить
int - тривиальный тип, его можно копировать через std::memcpy/std::memmove. Не говоря уже о том, что это все можно переписать на std::valarray в 2 строчки. Я бы советовал вам язык подучить, прежде чем лезть в алгоритмы и абстракции, ибо из-за того, что вы вручную делаете столько рутинных операций, ваш код превращается в простыню, и его довольно трудно читать и вам, и другим. Добавлено через 1 час 18 минут И вообще весь код надо бы разделить на две части: Класс матрицы (отвечает за рутину: копирование, создание/удаление) на основе std::valarray.Класс графа. А то у вас в коде куча лишних new и delete в цикле.Это очень сильно бьет по производительности, отдельный класс-обертка над std::valarray это исправит.Добавлено через 3 минуты Если говорить еще проще, ваш класс графа делает то, чем он заниматься не должен. Если сделать все, как я написал, вам будет проще добавлять функционал, в котором алгоритмическая составляющая на первом месте, а значит, выполнять задания.
1
|
|||||||||||||
|
Вездепух
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
|
|||
| 04.01.2024, 07:33 | |||
|
А чего вы ожидали? У вас в исходной матрице смежности много нулей. В результате получается, что практически между любыми двумя вершинам существует путь из нулевых ребер. Ноль - это ведь кратчайший, короче некуда, правда? Вот алгоритм Флойда-Уоршелла радостно и находит такие пути. Для вашей матрицы смежности все нули - это правильный ответ. Почему вас это удивляет? Собственно, вопрос в том, почему у вас в матрице смежности сидят нули? Что они означают? Судя по комментариям в вашем коде, отсутствующие ребра обозначаются через INT_MAX. Ну тогда ноль - это обычное ребро нулевого веса. У вас в матрице никаких INT_MAX нет вообще. То есть граф полный - все ребра без исключения присутствуют и многие из них имеют нулевой вес. Ну так неудивительно, что все кратчайшие пути оказались нулевыми. Так и есть. Это правильный ответ.
1
|
|||
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
|
||||||||||||
| 04.01.2024, 08:06 | ||||||||||||
Graph::addEdges:
Но код все равно "попахивает", причем сильно.
0
|
||||||||||||
|
Вездепух
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
|
|||||||
| 04.01.2024, 08:10 | |||||||
Сообщение было отмечено syperdog как решение
РешениеНули там сидели изначально:
main лишь заменяют некоторые из них на "ненули".Исходная матрица выглядит так: Вот они, нулики. P.S. У ТС в функции Graph::printVerticesAndEdges() признаком отсутствия ребра считается 0. А в Graph::floydWarshall() признаком отсутствия ребра считается INT_MAX. Вот из-за этой каши все и проблемы.
1
|
|||||||
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
|
|
| 04.01.2024, 08:14 | |
|
0
|
|
|
Вездепух
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
|
|||||||
| 04.01.2024, 08:27 | |||||||
|
Вообще-то вся идея, весь смысл использования огромного guard-значения, вроде INT_MAX, для обозначения отсутствующих ребер как раз и заключается в том, чтобы устранить необходимость делать
std::min, т.е. никакого дополнительного if не нужно (однако следить за переполнениями - нужно).А применить INT_MAX и потом еще все таки возиться с дополнительными if - это уже профанация и непонимание идеи.
1
|
|||||||
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
|
|
| 04.01.2024, 08:30 | |
|
TheCalligrapher, еще раз подтверждается моя подпись...
0
|
|
|
6218 / 2914 / 1046
Регистрация: 01.06.2021
Сообщений: 10,778
|
|
| 05.01.2024, 17:14 | |
|
IMHO, если в коде используется INT_MAX или что-нибудь похожее, то это признак плохого качества
0
|
|
|
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
|
|
| 06.01.2024, 01:10 | |
|
Плохого качества чего ?
--- Хинт : Использование любого значения из диапазона в качестве контрольного - частая практика.
1
|
|
|
6218 / 2914 / 1046
Регистрация: 01.06.2021
Сообщений: 10,778
|
|
| 06.01.2024, 02:51 | |
|
SmallEvil, плохое качество алгоритма. Только на этом форуме видел много раз, как из-за этих предельных значений возникало много ошибок. Порой, эти значения ошибочно даже участвовали в вычислениях, тогда как они должны были служить для проверок. Иногда из-за них случались переполнения.
0
|
|
|
Вездепух
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
|
|
| 06.01.2024, 04:54 | |
|
В данном случае, конечно же, для того, чтобы использовать большое значение в качестве guard-значения, нужно было либо использовать в этой роли
INT_MAX / 2, либо суммирование и сравнение расстояний выполнять в рамках более широкого типа.А в текущем варианте из-за INT_MAX получилось переполнение, которое принялись лечить через дополнительный if. В результате чего сразу возникает вопрос о том, к чему тут вообще INT_MAX, если для обозначения отсутствующих ребер уже ранее был выбран 0.
1
|
|
|
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
|
|
| 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
Алгоритм Флойда-Уоршелла Алгоритм Флойда-Уоршелла Алгоритм Флойда — Уоршелла Алгоритм Флойда-Уоршелла Алгоритм Флойда-Уоршелла Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога
Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip
На первой гифке отладочные линии отключены, а на второй включены:. . .
|
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога
Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536
Одним из. . .
|
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
|
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
|
|
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
|
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога
Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
|
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование
. \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json>
Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом.
# Check if. . .
|
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так:
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347
Основана на STM32F303RBT6.
На борту пять. . .
|