Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/14: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Healius
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
1

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

07.05.2011, 14:47. Просмотров 2477. Ответов 2
Метки нет (Все метки)

код:
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 минут
народ, неужели никто не может помочь?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.05.2011, 14:47
Ответы с готовыми решениями:

Теория графов
Есть задание. найти максимальное и среднее расстояние между центральными...

Теория графов. Найти время
Здравствуйте. Новичок. Впервые столкнулся с графами. Есть вот такая задача:...

Теория графов. Задача Обрати меня!
Мальчик Вася очень любит разворачивать ориентированные графы. Помогите ему в...

Алгоритм Флойда-Уоршела
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он...

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

2
Ultrator
14 / 10 / 1
Регистрация: 28.04.2009
Сообщений: 219
08.05.2011, 06:20 2
Ну а, что в 22 строке, k=1 - так и должно быть?
0
Healius
4 / 4 / 2
Регистрация: 06.05.2011
Сообщений: 50
08.05.2011, 16:11  [ТС] 3
ну да, K обозначает шаг действия алгоритма, нулевой шаг уже сделан
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.05.2011, 16:11

Алгоритм Флойда Оршала
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой...

Алгоритм Флойда С++ реализация
Есть такой код класса Помогите, пожалуйста найти по методу Флойда самый...

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n;...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru