Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
Healius
4 / 4 / 0
Регистрация: 06.05.2011
Сообщений: 50
#1

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

18.05.2011, 10:59. Просмотров 1660. Ответов 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 минут
ап...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2011, 10:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Шимбелла (C++):

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм - Pascal
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что будет напечатано программой Program...

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида) - Алгоритмы
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова,...

1
igor0802
0 / 0 / 0
Регистрация: 22.12.2011
Сообщений: 27
23.12.2011, 11:01 #2
У меня такая же задача, и никакого ответа!!((
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.12.2011, 11:01
Привет! Вот еще темы с ответами:

Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке [a,b] с шагом h. - Free Pascal
Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке с шагом h. Написать программу: F=3+tgx Мой...

Построить алгоритм ДО и алгоритм ПОКА дя вычислений значения функции на отрезке [а,b] с шагом h. Написать программу - Pascal
F=3+tg x

Составить алгоритм-вычисление квадрата суммы двух чисел и алгоритм для вычисления функции - Pascal ABC
Здравствуйте!Мне нужно все с самого начала и точно,помогите пожалуйста! 1.составить алгоритм-вычисление квадрата суммы двух чисел.

Написать алгоритм по блок схеме (Алгоритм метода Ньютона) - Pascal
Прошу помогите, очень срочно! Сижу на экзамене!


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

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

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