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

Алгоритм Флойда - Уоршелла - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Найти сумму элементов строки матрицы, в которой расположен элемент с наименьшим значением http://www.cyberforum.ru/cpp-beginners/thread210108.html
ребята очень нужна помощь при выводе матрицы.Кто сможет помоч если сможет.Нада MFC AppWizard.exe проект и вот задание Дана действительная матрица размера m*n. Найти сумму элементов строки, в...
C++ Сравнение методов сортировок массивов. Семестровая работа Пишу семестровую по методам сортировки массивов. В моем варианте метод прямого выбора и метод Шейкера. Надо сравнить количество перестановок для различного числа элементов массива. n = 20,... http://www.cyberforum.ru/cpp-beginners/thread210105.html
При чтении файла последний элемент повторяется дважды C++
появилась необходимость выучить работу с файлами за 9 часов #include <iostream> #include <time.h> #include <stdio.h> #include <stdlib.h> int main() {
Расчет средневзвешенной оценки C++
Написать программу для расчёта средневзвешенной оценки по предмету, средневзвешенной называетсяоценка, складывающаяся из 5 текущих оценок, но каждая из оценок имеет "вес" (коэффициент от 0 до 1)....
C++ Структура / системы координат http://www.cyberforum.ru/cpp-beginners/thread210094.html
Здраствуйте уважаемые знатоки! Есть задача по структурам: Надо описать структуры для декартовых (x,y) и полярных (r,pi) координат. Определить функцию для перевода из полярных в декартовы...
C++ Завернутые векторы Нужно написать програму, которая складывает два завернутых вектора фиксированной длинны. Вообщем прграма из трех файлов, выдает ошибку Linking... main.obj : error LNK2001: unresolved external... подробнее

Показать сообщение отдельно
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,542
Завершенные тесты: 3
13.12.2010, 19:23
White Luna, Там вся программа алгоритм Флойда Уоршалла...

Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
       void Fill()
        {
                for(size_t i=0; i<Matr.size(); ++i)
                {
                        for(size_t j=0; j<Matr.size(); ++j)
                        {
                                if(i==j)
                                        Matr[i][j]=0;
                                else if(i>j)
                                {
                                        Matr[i][j]=Matr[j][i];
                                }
                                else
                                {
                                        std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                                                <<"0 for not connect them\n";
                                        std::cin>>Matr[i][j];
                                        if(Matr[i][j]==0)
                                                Matr[i][j]=100;
                                }
                        }
                }
        }
Это заполнение матрицы смежности.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        void Initialise()
        {
                MatrPath.resize(Matr.size());
                for(size_t i=0; i<Matr.size(); ++i)
                        MatrPath[i].resize(Matr.size());
                for(size_t i=0; i<MatrPath.size(); ++i)
                {
                        for(size_t j=0; j<MatrPath.size(); ++j)
                        {
                                if(Matr[i][j]==100)
                                        MatrPath[i][j]=100;
                                else
                                        MatrPath[i][j]=j;
                        }
                }
                Copy();
        }
Это создание матрицы путей.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
        void FindPathMatr()
        {
                for(size_t k=0; k<Matr.size(); ++k)
                {
                        for(size_t i=0; i<Matr.size(); ++i)
                        {
                                for(size_t j=0; j<Matr.size(); ++j)
                                {
                                        int b=MatrSPath[i][k]+MatrSPath[k][j];
                                        if(b<MatrSPath[i][j])
                                        {
                                                MatrSPath[i][j]=b;
                                                MatrPath[i][j]=k;
                                        }
                                }
                        }
                }
        }
Инициализация матрицы кратчайших путей нужными значениями.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
        void FindPath(size_t first, size_t second)
        {
                if(first>=MatrPath.size() || second>=MatrPath.size())
                        throw std::invalid_argument("One of nodes for searching is more than Matr size");
                ST Goals;
                Path.push(first);
                Goals.push(second);
                while(!Goals.empty())
                {
                        int u=Path.top();
                        int v=Goals.top();
                        int s=MatrPath[u][v];
                        if(v==s)
                        {
                                Path.push(v);
                                Goals.pop();
                        }
                        else
                                Goals.push(s);
                }
        }
Это нахождение пути от вершины к другой вершине. Вершины вводятся из main-а с клавиатуры. Через два стека. Не самый оптимальный алгоритм. У меня есть оптимальнее на бумаге, но переделывать пока лень.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru