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

Алгоритм Шимбелла - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
18.05.2011, 10:59     Алгоритм Шимбелла #1
Алгоритм Шимбелла позволяет находить минимальные (максимальные)
пути между вершинами, состоящие из заданного количества ребер.
Введем специальные операции над элементами матрицы:
1) Операция умножения двух величин а и b при возведении матрицы в
степень соответствует их алгебраической сумме:
2) Операция сложения двух величин а и b заменяется выбором из этих
величин минимального (максимального) элемента:
Нули при этом игнорируются. Минимальный (максимальный) элемент
выбирается из ненулевых элементов. Ноль в результате операции может быть
получен лишь тогда, когда все элементы нулевые.
С помощью этих операций длины минимальных (максимальных) путей
определяются возведением в степень весовой матрицы Ω.

помогите реализовать на 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
int** shimbell(int** W,int n,int kol){
    if(kol==0)
        return W;
    else{
        int** temp=new int*[n];
        int** c=new int*[n];
        for(int i=0;i<n;i++){
            temp[i]=new int[n];
            c[i]=new int[n];
            for(int j=0;j<n;j++){
                c[i][j]=W[i][j];
                temp[i][j]=W[i][j];
            }
        }
        for(int r=0;r<kol;r++){
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    for(int k=0;k<n;k++){
                        c[i][j]+=plus_sh(temp[i][k],W[k][j]);
                    }
            temp=c;
        }
        return c;
    }
}
В параметрах функции: W-матрица весов графа, n-её размерность, kol-количество ребер в нужных максимальных/минимальных путях. (соответствует степени, в которую надо возвести матрицу с учетом операций Шимбелла). код выдает неправильные результаты, ошибку не найти никак %)

Добавлено через 1 час 10 минут
функция plus_sh - реализация операции сложения по Шимбеллу
C++
1
2
3
4
5
6
7
8
9
10
11
12
int plus_sh(int a,int b){
    if((a==0)&&(b==0))
        return 0;
    else{
        if(a==0)
            return b;
        if(b==0)
            return a;
        else
            return min(a,b);
    }
}
ЗЫ: да, коряво написано...%)

Добавлено через 4 часа 27 минут
да что ж так у всех с графами плохо...?

Добавлено через 2 часа 28 минут
ап...

Добавлено через 18 часов 47 минут
ап...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2011, 10:59     Алгоритм Шимбелла
Посмотрите здесь:

C++ c++/алгоритм
алгоритм C++
алгоритм C++
C++ Алгоритм
Алгоритм C++
C++ Алгоритм А*
C++ Алгоритм
C++ алгоритм бм

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
igor0802
0 / 0 / 0
Регистрация: 22.12.2011
Сообщений: 26
23.12.2011, 11:01     Алгоритм Шимбелла #2
У меня такая же задача, и никакого ответа!!((
Yandex
Объявления
23.12.2011, 11:01     Алгоритм Шимбелла
Ответ Создать тему
Опции темы

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