1 / 1 / 0
Регистрация: 14.02.2021
Сообщений: 173
1

Как реализовать алгоритм Флойда, матрица смежности которого, представлена одномерным массивом?

20.12.2022, 18:41. Показов 402. Ответов 4
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <sys/time.h>
 
#define SIZE 1000
 
int main() {
 
  int *Matrix = new int[SIZE * SIZE];
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      Matrix[i * SIZE + j] = rand() % 100;
    }
 
    delete[] Matrix;
  }
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.12.2022, 18:41
Ответы с готовыми решениями:

Как реализовать алгоритм Флойда-Уоршелла на C++
Псевдокод есть { for (int k = 0; k &lt; n; k++) for (int i = 0; i &lt; n; i++)...

Как реализовать алгоритм Флойда Уоршелла
Добрый день. Как реализовать алгоритм Флойда Уоршелла Вот сама задача На карте, представленной в...

Для бинарной матрицы смежности нужно построить матрицу достижимости (алгоритм Флойда)
Для бинарной матрицы смежности нужно построить матрицу достижимости. Все делаю как в вики, но...

Алгоритм задачи с одномерным массивом
Исходные данные: массив чисел Х размером n. Задание: Ввести исходный массив с клавиатуры,...

Реализовать модуль , работающий с одномерным массивом
Я в массивах нуб , поэтому прошу Вас помочь ... Дали такое задание.. Реализовать модуль ,...

4
4761 / 2571 / 891
Регистрация: 29.11.2010
Сообщений: 5,551
20.12.2022, 19:02 2
Цитата Сообщение от Noob_03 Посмотреть сообщение
матрица смежности которого ... представлена одномерным массивом
И в чём разница? У вас же даже есть пример, как к ней адресоваться. оО
0
1 / 1 / 0
Регистрация: 14.02.2021
Сообщений: 173
20.12.2022, 19:09  [ТС] 3
Так будет верно?
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
#include <iostream>
#include <sys/time.h>
 
#define SIZE 1000
 
int main() {
 
  int *Matrix = new int[SIZE * SIZE];
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      Matrix[i * SIZE + j] = rand() % 100;
    }
  }
 
  for (int k = 0; k < SIZE; k++) {
    for (int i = 0; i < SIZE; i++) {
      for (int j = 0; j < SIZE; j++) {
        Matrix[i * SIZE + j] =
            std::min(Matrix[i * SIZE + j], Matrix[i * SIZE + k] + Matrix[j]);
      }
    }
  }
  delete[] Matrix;
}
0
4761 / 2571 / 891
Регистрация: 29.11.2010
Сообщений: 5,551
20.12.2022, 19:38 4
Лучший ответ Сообщение было отмечено Noob_03 как решение

Решение

Цитата Сообщение от Noob_03 Посмотреть сообщение
+ Matrix[j]
Вот тут не похоже на правду.
Минимальное должно искаться (в вашем случае) из [i][j] и суммы [i][k]+[k][j],
соответственно должно быть что-то вроде:
std::min(Matrix[i * SIZE + j], Matrix[i * SIZE + k] + Matrix[k * SIZE + j]);

Добавлено через 3 минуты
Остальное навскидку должно сработать.

Добавлено через 1 минуту
Цитата Сообщение от Noob_03 Посмотреть сообщение
#include <sys/time.h>
А это что и зачем? Имелось в виду #include <ctime> для дальнейшей инициализации устаревшего генератора случайных чисел зерном из текущего времени?
В целом по коду устаревший подход к рандому, не сильно удачный выбор типов переменных и способ задания констант, но вот именно так сработать должно.

Цитата Сообщение от Noob_03 Посмотреть сообщение
#define SIZE 1000
Напомню, что алгоритм сделает SIZE^3 итераций. Придётся немного подождать.

Добавлено через 8 минут
Осовременивание
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
#include <iostream>
#include <chrono> // современная библиотека работы со временем (ей 11 лет уже)
#include <random> // современная библиотека работы со случайными числами (ей тоже 11 лет уже)
 
 
int main() {
    // генератор псевдо-случайных чисел, инициализированный зерном -- количеством милисекунд с начала эпохи UNIX
    std::default_random_engine randomEngine(std::chrono::system_clock::now().time_since_epoch().count());
    // функтор для получения равномерно распределённых случайных чисел из генератора в заданном диапазоне
    // это используется вместо rand() % 100, который не распределяет значения равномерно
    std::uniform_real_distribution<double> randomWeight(0, 1000);
 
    // Не нужен дефайн, достаточно банальной переменной
    // маленькими буквами -- из моего любимого кодстайла
    std::size_t size = 100; // тыща много -- не люблю ждать
    // тут удобнее выбрать double из-за того, что у него есть значение infinity
    // имя с маленькой буквы -- из моего любимого кодстайла
    double *matrix = new double[size * size];
    // тип индексов при адресации имеет имя size_t (оно же std::size_t)
    for (std::size_t i = 0; i < size; i++) {
        for (std::size_t j = 0; j < size; j++) {
            // получение случайного значения используя современные средства
            matrix[i * size + j] = randomWeight(randomEngine);
        }
    }
 
    for (std::size_t k = 0; k < size; k++) {
        for (std::size_t i = 0; i < size; i++) {
            for (std::size_t j = 0; j < size; j++) {
                matrix[i * size + j] =
                        std::min(matrix[i * size + j], matrix[i * size + k] + matrix[k * size + j]);
            }
        }
    }
    delete[] matrix;
}
1
1 / 1 / 0
Регистрация: 14.02.2021
Сообщений: 173
20.12.2022, 20:04  [ТС] 5
У меня задача распараллелить программу при помощи MPI
0
20.12.2022, 20:04
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.12.2022, 20:04
Помогаю со студенческими работами здесь

Как лучше всего реализовать параллельную версию программы для поиска кротчайших путей (алгоритм Флойда)?
Есть последовательная программа, в которой реализован алгоритм Флойда, но нужно реализовать...

Алгоритм Флойда, матрица предков
Добрый день! Имеется следующий граф: Для него необходимо вычислить все наикратчайшие пути...

Реализовать выполнение заданных действий над одномерным массивом.
&quot;Реализовать выполнение заданных действий над одномерным массивом. Число элементов массива задаётся...

Реализовать алгоритм Флойда-Уоршалла
Здравствуйте. Я понимаю, что уже неоднократно разбирался алгоритм Флойда-Уоршалла, но у меня всё...

Реализовать алгоритм Флойда Уоршелла
Нужна помощь по написанию алгоритма по задаче представленной ниже: Туристическая фирма...

реализовать в виде программы алгоритм Флойда-Уоршелла
Разработать и реализовать в виде программы алгоритм Флойда-Уоршелла для заданного графа с числом...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru