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

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

03.01.2024, 06:26. Показов 2603. Ответов 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
Сообщений: 129
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
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
04.01.2024, 07:33
Цитата Сообщение от syperdog Посмотреть сообщение
Проблема с выводом
Почему вы решили, что проблема именно с выводом? Или вы вообще все проблемы "проблемами с выводом" считаете? Нет вывода - нет проблемы?

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

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

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

Собственно, вопрос в том, почему у вас в матрице смежности сидят нули? Что они означают? Судя по комментариям в вашем коде, отсутствующие ребра обозначаются через INT_MAX. Ну тогда ноль - это обычное ребро нулевого веса. У вас в матрице никаких INT_MAX нет вообще. То есть граф полный - все ребра без исключения присутствуют и многие из них имеют нулевой вес. Ну так неудивительно, что все кратчайшие пути оказались нулевыми. Так и есть. Это правильный ответ.
1
27 / 24 / 4
Регистрация: 20.11.2023
Сообщений: 129
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
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
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
Сообщений: 129
04.01.2024, 08:14
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
некоторые из них
Да, ошибся
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12930 / 6798 / 1819
Регистрация: 18.10.2014
Сообщений: 17,198
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
Сообщений: 129
04.01.2024, 08:30
TheCalligrapher, еще раз подтверждается моя подпись...
0
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6136 / 2830 / 1039
Регистрация: 01.06.2021
Сообщений: 10,324
05.01.2024, 17:14
IMHO, если в коде используется INT_MAX или что-нибудь похожее, то это признак плохого качества
0
Заблокирован
06.01.2024, 01:10
Плохого качества чего ?
---
Хинт : Использование любого значения из диапазона в качестве контрольного - частая практика.
1
Эксперт функциональных языков программированияЭксперт С++
 Аватар для Royal_X
6136 / 2830 / 1039
Регистрация: 01.06.2021
Сообщений: 10,324
06.01.2024, 02:51
SmallEvil, плохое качество алгоритма. Только на этом форуме видел много раз, как из-за этих предельных значений возникало много ошибок. Порой, эти значения ошибочно даже участвовали в вычислениях, тогда как они должны были служить для проверок. Иногда из-за них случались переполнения.
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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
Ответ Создать тему
Новые блоги и статьи
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
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 - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru