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

Алгоритм Флойда (теория графов) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
07.05.2011, 14:47     Алгоритм Флойда (теория графов) #1
код:
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
int** floid(int** W,int n){
    vector<int**>D(n);
    int** A=new int*[n];
    for(int i=0;i<n;i++){
        A[i]=new int[n];
        for(int j=0;j<n;j++)
            A[i][j]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)
                A[i][j]=0;
            else{
                if(W[i][j]==0)
                    A[i][j]=100;
                else
                    A[i][j]=W[i][j];
            }
        }
    }
    D.push_back(A);
    int k=1;
    while(k<n){
        int** B=new int*[n];
        for(int i=0;i<n;i++){
            B[i]=new int[n];
            for(int j=0;j<n;j++)
                B[i][j]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j)
                    B[i][j]=min(D.back()[i][j],(D.back()[i][k]+D.back()[k][j]));
            }
        }
        k++;
        D.push_back(B);
    }
    return D.back();
}
на выходе должна быть матрица длин кратчайших путей, в пункции параметры - матрица весов графа и её размерность. проблема: алгоритм не видит пути через 0-ю вершину. подскажите плиз, в чем дело? остальные пути нормально вычисляет, алгоритм написан верно.

Добавлено через 16 часов 59 минут
народ, неужели никто не может помочь?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.05.2011, 14:47     Алгоритм Флойда (теория графов)
Посмотрите здесь:

C++ В чем ошибка? Алгоритм Флойда
C++ Алгоритм Флойда - Уоршелла
Алгоритм Флойда-Уоршелла (результат работы неправильный) C++
C++ Алгоритм Флойда–Уоршелла
Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. C++
C++ Алгоритм Флойда Оршала
Теория графов C++
Алгоритм Флойда-Уоршела C++
C++ Алгоритм Флойда-Уоршалла граф
C++ Теория графов. Задача Обрати меня!
Алгоритм Джонсона для графов C++
Алгоритм Флойда С++ реализация C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
08.05.2011, 06:20     Алгоритм Флойда (теория графов) #2
Ну а, что в 22 строке, k=1 - так и должно быть?
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
08.05.2011, 16:11  [ТС]     Алгоритм Флойда (теория графов) #3
ну да, K обозначает шаг действия алгоритма, нулевой шаг уже сделан
Yandex
Объявления
08.05.2011, 16:11     Алгоритм Флойда (теория графов)
Ответ Создать тему
Опции темы

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