Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/13: Рейтинг темы: голосов - 13, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 25.10.2021
Сообщений: 8

Проблема с выводом алгоритма Флойда — Уоршелла

03.01.2024, 06:26. Показов 2616. Ответов 12
Метки c++ (Все метки)

Студворк — интернет-сервис помощи студентам
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
45
46
47
48
49
50
51
52
void Graph::floydWarshall()
{
    int** dist = new int* [vertices];
    for (int i = 0; i < vertices; ++i)
    {
        dist[i] = new int[vertices];
        for (int j = 0; j < vertices; ++j)
        {
            dist[i][j] = matrix[i][j];
        }
    }
 
    for (int k = 0; k < vertices; ++k)
    {
        for (int i = 0; i < vertices; ++i)
        {
            for (int j = 0; j < vertices; ++j)
            {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
 
    // Выведите кратчайшие расстояния
    cout << "Кратчайшее расстояние между вершинами: " << endl;
    for (int i = 0; i < vertices; ++i)
    {
        for (int j = 0; j < vertices; ++j)
        {
            if (dist[i][j] == INT_MAX)
            {
                cout << "INF ";
            }
            else
            {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
 
    // Очистка памяти
    for (int i = 0; i < vertices; ++i)
    {
        delete[] dist[i];
    }
    delete[] dist;
}
Задание: нужно сделать Алгоритм Флойда — Уоршелла, в графе представленного в виде матрицы смежности, я попытался реализовать данный алгоритм и вроде бы всё нормально как в псевдокоде в интернете, но при выводе почему-то выводит одни нули либо только расстояние с ближайшими вершинами. Не могу понять почему так происходит.(исходные файлы скинул в закреп).
Вложения
Тип файла: txt main.txt (443 байт, 10 просмотров)
Тип файла: txt head.txt (296 байт, 9 просмотров)
Тип файла: txt funtion.txt (2.4 Кб, 10 просмотров)
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
03.01.2024, 06:26
Ответы с готовыми решениями:

Реализация Алгоритма Флойда-Уоршелла
Здравствуйте Пытаюсь реализовать основную программы функцию алгоритма Флойда-Уоршела нашёл пример .exe в интернете и взял его как...

Задача коммивояжера с использованием алгоритма Флойда-Уоршелла
Здравствуйте. Возможно ли решить задачу коммивояжера при помощи алгоритма Флойда-Уоршелла?

Алгоритм Флойда-Уоршелла
Задача: найти медиану графа, т.е такую его вершину. что сумма расстояний от нее до остальных вершин минимальна. Я пока пытаюсь найти...

12
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
03.01.2024, 12:51
Решение:
попробуйте заменить
Цитата Сообщение от syperdog Посмотреть сообщение
C++
1
2
3
4
5
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
 dist[i][k] + dist[k][j] < dist[i][j])
 {
 dist[i][j] = dist[i][k] + dist[k][j];
 }
На
C++
1
2
          if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)
                dist[i][j] = std::min(d[i][j], dist[i][k] + dist[k][j]);
И сверху добавить
C++
1
#include <cmath>
Рекомендации:
Цитата Сообщение от syperdog Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
int** dist = new int* [vertices];
 for (int i = 0; i < vertices; ++i)
 {
 dist[i] = new int[vertices];
 for (int j = 0; j < vertices; ++j)
 {
 dist[i][j] = matrix[i][j];
 }
 }
Зачем так заморачиваться с копированием? int - тривиальный тип, его можно копировать через std::memcpy/std::memmove. Не говоря уже о том, что это все можно переписать на std::valarray в 2 строчки.
Я бы советовал вам язык подучить, прежде чем лезть в алгоритмы и абстракции, ибо из-за того, что вы вручную делаете столько рутинных операций, ваш код превращается в простыню, и его довольно трудно читать и вам, и другим.

Добавлено через 1 час 18 минут
И вообще весь код надо бы разделить на две части:
Класс матрицы (отвечает за рутину: копирование, создание/удаление) на основе std::valarray.
Класс графа.
А то у вас в коде куча лишних new и delete в цикле.
Это очень сильно бьет по производительности, отдельный класс-обертка над std::valarray это исправит.

Добавлено через 3 минуты
Если говорить еще проще, ваш класс графа делает то, чем он заниматься не должен.
Если сделать все, как я написал, вам будет проще добавлять функционал, в котором алгоритмическая составляющая на первом месте, а значит, выполнять задания.
1
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
04.01.2024, 07:33
Цитата Сообщение от syperdog Посмотреть сообщение
Проблема с выводом
Почему вы решили, что проблема именно с выводом? Или вы вообще все проблемы "проблемами с выводом" считаете? Нет вывода - нет проблемы?

Цитата Сообщение от syperdog Посмотреть сообщение
но при выводе почему-то выводит одни нули
Что насчитали - то и вывели.

А чего вы ожидали? У вас в исходной матрице смежности много нулей. В результате получается, что практически между любыми двумя вершинам существует путь из нулевых ребер. Ноль - это ведь кратчайший, короче некуда, правда? Вот алгоритм Флойда-Уоршелла радостно и находит такие пути. Для вашей матрицы смежности все нули - это правильный ответ.

Почему вас это удивляет?

Собственно, вопрос в том, почему у вас в матрице смежности сидят нули? Что они означают? Судя по комментариям в вашем коде, отсутствующие ребра обозначаются через INT_MAX. Ну тогда ноль - это обычное ребро нулевого веса. У вас в матрице никаких INT_MAX нет вообще. То есть граф полный - все ребра без исключения присутствуют и многие из них имеют нулевой вес. Ну так неудивительно, что все кратчайшие пути оказались нулевыми. Так и есть. Это правильный ответ.
1
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
04.01.2024, 08:06
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
У вас в исходной матрице смежности много нулей
В main'е:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    Graph g(6);
    g.addEdges(0, 1, 7);
    g.addEdges(0, 2, 9);
    g.addEdges(0, 5, 14);
    g.addEdges(1, 2, 10);
    g.addEdges(1, 3, 15);
    g.addEdges(2, 3, 11);
    g.addEdges(2, 5, 2);
    g.addEdges(3, 4, 6);
    g.addEdges(4, 5, 9);
    g.printVerticesAndEdges();
    cout << endl;
 
    g.floydWarshall();
    return 0;
Graph::addEdges:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void Graph::addEdges(int u, int v, int weight)
{
    if (weight > 0 && u < vertices && v < vertices)
    {
        matrix[v][u] = weight;
        matrix[u][v] = weight;
    }
    else if (u < vertices && v < vertices)
    {
        matrix[v][u] = INT_MAX;  // Устанавливается как бесконечность для отсутствующих ребер
        matrix[u][v] = INT_MAX;
    }
}
Вроде бы нулей там не должно быть.
Но код все равно "попахивает", причем сильно.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
04.01.2024, 08:10
Лучший ответ Сообщение было отмечено syperdog как решение

Решение

Цитата Сообщение от pechka_ne_sed Посмотреть сообщение
Вроде бы нулей там не должно бытью
Что значит "не должно быть"?

Нули там сидели изначально:

C++
1
2
3
4
5
6
7
8
9
10
11
12
Graph::Graph(int v) : vertices(v)
{
    matrix = new int* [vertices];
    for (int i = 0; i < vertices; i++)
    {
        matrix[i] = new int[vertices];
        for (int j = 0; j < vertices; j++)
        {
            matrix[i][j] = 0;
        }
    }
}
а процитированные вами вызовы в main лишь заменяют некоторые из них на "ненули".

Исходная матрица выглядит так:

Название: Screenshot 2024-01-03 211248.png
Просмотров: 107

Размер: 3.2 Кб

Вот они, нулики.

P.S. У ТС в функции Graph::printVerticesAndEdges() признаком отсутствия ребра считается 0. А в Graph::floydWarshall() признаком отсутствия ребра считается INT_MAX. Вот из-за этой каши все и проблемы.
1
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
04.01.2024, 08:14
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
некоторые из них
Да, ошибся
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12938 / 6805 / 1821
Регистрация: 18.10.2014
Сообщений: 17,227
04.01.2024, 08:27
Цитата Сообщение от pechka_ne_sed Посмотреть сообщение
Решение:
попробуйте заменить

На
C++
1
2
          if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)
                dist[i][j] = std::min(d[i][j], dist[i][k] + dist[k][j]);
Безобразие.

Вообще-то вся идея, весь смысл использования огромного guard-значения, вроде INT_MAX, для обозначения отсутствующих ребер как раз и заключается в том, чтобы устранить необходимость делать

C++
1
if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)
Вся идея "бесконечного" значения как раз и заключается в том, что такие значения уже сами по себе не смогут "выиграть" в std::min, т.е. никакого дополнительного if не нужно (однако следить за переполнениями - нужно).

А применить INT_MAX и потом еще все таки возиться с дополнительными if - это уже профанация и непонимание идеи.
1
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 131
04.01.2024, 08:30
TheCalligrapher, еще раз подтверждается моя подпись...
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6218 / 2914 / 1046
Регистрация: 01.06.2021
Сообщений: 10,778
05.01.2024, 17:14
IMHO, если в коде используется INT_MAX или что-нибудь похожее, то это признак плохого качества
0
 Аватар для SmallEvil
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
06.01.2024, 01:10
Плохого качества чего ?
---
Хинт : Использование любого значения из диапазона в качестве контрольного - частая практика.
1
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6218 / 2914 / 1046
Регистрация: 01.06.2021
Сообщений: 10,778
06.01.2024, 02:51
SmallEvil, плохое качество алгоритма. Только на этом форуме видел много раз, как из-за этих предельных значений возникало много ошибок. Порой, эти значения ошибочно даже участвовали в вычислениях, тогда как они должны были служить для проверок. Иногда из-за них случались переполнения.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
09.01.2024, 16:33
Помогаю со студенческими работами здесь

Алгоритм Флойда-Уоршелла
Народ подскажите , а как реализовать этот алгоритм на Delphi ?

Алгоритм Флойда-Уоршелла
У меня есть задание....дан граф, представленный матрицей смежности. Для каждой пары вершин определить, существует ли кратчайший путь между...

Алгоритм Флойда — Уоршелла
Мне нужно подсчитать сумму кротчайшего пути от вершины А к вершине В. При этом не нужно брать в расчеты 0 (нули).

Алгоритм Флойда-Уоршелла
using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApp36 { class Program { ...

Алгоритм Флойда-Уоршелла
Вечно какая-то засада и кругом враги! :-) Разбирался я в алгоритме Уоршелла. И вот какая проблема: моё решение выводит не те параметры,...


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

Или воспользуйтесь поиском по форуму:
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&amp;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. На борту пять. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru