Форум программистов, компьютерный форум CyberForum.ru

Алгоритм Флойда-Уоршелла (результат работы неправильный) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
liliya
0 / 0 / 0
Регистрация: 08.10.2011
Сообщений: 5
08.11.2011, 21:26     Алгоритм Флойда-Уоршелла (результат работы неправильный) #1
Задание выглядит так:

Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

Пример
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0
где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса
ответ - 16, у меня - 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
 
using namespace std;
#define M 123456789
const int INF = 0;
int main()
{
    int V_min, TS = M, S, N, A[100][100] = {};
    cin >> N; // Ввод количества вершин
    // Ввод матрицы смежности
    for ( int i = 0; i < N; ++i )
        for ( int j = 0; j < N; ++j )
        {
            cin >> A[i][j];
            if ( A[i][j] == 0 )
                A[i][j] = M;
        }
    // Алгоритм Флойда-Уоршелла
    for ( int k = 0; k < N; ++k )
        for ( int i = 0; i < N; ++i )
            for ( int j = 0; j < N; ++j )
                if (A[i][k] < INF && A[k][j] < INF)
                A[i][j] = min (A[i][j], A[i][k] + A[k][j]);
             
    // Ищем вершину с минимальной суммой
    for ( int i = 0; i < N; ++i )
    {
        S = 0;
        for ( int j = 0; j < N; ++j )
            S += A[i][j];
        if ( S < TS )
        {
            TS = S;
            V_min = i;
        }
    }
    cout << V_min; 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.11.2011, 21:26     Алгоритм Флойда-Уоршелла (результат работы неправильный)
Посмотрите здесь:

C++ Алгоритм Флойда - Уоршелла
Неправильный результат C++
C++ Алгоритм Флойда–Уоршелла
C++ Неправильный результат
C++ Алгоритм Флойда Оршала
Алгоритм Флойда-Уоршела C++
Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла C++
Не могу найти ошибку в алгоритме Флойда-Уоршелла C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-comrade-
355 / 356 / 42
Регистрация: 11.06.2010
Сообщений: 703
09.11.2011, 01:14     Алгоритм Флойда-Уоршелла (результат работы неправильный) #2
liliya, смотрите.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
09.11.2011, 01:55     Алгоритм Флойда-Уоршелла (результат работы неправильный) #3
liliya, зачем нужна строка №5, если уже есть строка №4?
Строка №15: if ( A[i][j] < 0 ).
Строка №22 не нужна.
После #include <iostream> подключите еще #include <algorithm>
Yandex
Объявления
09.11.2011, 01:55     Алгоритм Флойда-Уоршелла (результат работы неправильный)
Ответ Создать тему
Опции темы

Текущее время: 00:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru