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

Как вывести матрицу смежности по заданной матрице весов дуг? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Тонкость с указателями - взятие указателя на базовый класс http://www.cyberforum.ru/cpp-beginners/thread730680.html
Как-то возник в голове вопрос: пусть класс D наследует классы A и B. Если у меня есть объект D, я беру его адрес и типизирую его к базовым классам A и B. Получаю два указателя типа A* и B*. Будут ли они указывать на корректные объекты? Я всегда предполагал, что конструкции типа: Type1 *a = (Type1*)b; это указания компилятору интерпретировать данные по указателю b как данные типа Type1. А...
C++ map<string, string>define_map нужно имитировать работу препроцессора #define у нас есть файл из которого считали программу на С++. list<string> word_list; list<string>::iterator i; string str; //заполняю word_list while(1){ getline(in,str); word_list.push_back(str); http://www.cyberforum.ru/cpp-beginners/thread730677.html
C++ не работает функция-счётчик
Функция должна возвращать целое значение, уменьшающееся на 1 при каждом вызове. Начальное значение равно 10 #include "stdafx.h" int main() { static int a=10; a--; printf("%d \n",a); return a; }
Минимальное дерево-остов C++
Ребят, помогите пожалуйста решить задачу в BC++ )) На плоскости своими координатами заданно n точек. Построить связный граф с вершинами во всех этих точках так, чтобы суммарная длина его ребер была наименьшей.
C++ как переделать программу? http://www.cyberforum.ru/cpp-beginners/thread730662.html
компилятор выдает много ошибок, как исправить ума не приложу. может быть что то нужно переделать? подскажите #include <stdlib.h> #include <conio.h> #include <math.h> void main() { double s, n, m, b, a, c, x, y, nm; cout <<"Vvedi a "; cin >> a;
C++ буквенная матрица в С++ помогите пожалуйста не могу сделать нужно создать буквенную матрицу при нажатии любой клавиши где i=j выводит букву О,i>j выводит-N,i<j выводит -Z, и при нажатии другой значения инвертируются : i>j выводит Z,i<j выводит -N. сделала но почему то не выводит букву О, и так же надо перевести формат cpp в exe? листинг: # include <iostream.h> # include <windows.h> # include <conio.h> #... подробнее

Показать сообщение отдельно
feanoris
0 / 0 / 0
Регистрация: 11.10.2012
Сообщений: 49
13.12.2012, 20:00     Как вывести матрицу смежности по заданной матрице весов дуг?
Программа, реализующая алгоритм Флойда для поиска кратчайшего пути. Пользователь вводит ко-во вершин, затем указывает веса дуг, если вершины не соединены, то вес дуг = 0. Выводится матрица весов. Как сделать, чтоды выводилась матрица смежностей после матрицы весов?
Floyd.h
Кликните здесь для просмотра всего текста
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#ifndef _FLOYD_H_
#define _FLOYD_H_
 
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
#include "stdafx.h"
#include <conio.h>
#include <fstream>
#include "windows.h"
#include <stdlib.h>
#include <cstdlib>
#include <string>
using namespace std;
using namespace System;
typedef std::vector<std::vector<int> > VM;
typedef std::stack<int> ST;
 
class MatrixAdj
{
public:
    MatrixAdj()
    {
    }
 
    virtual ~MatrixAdj()
    {
    }
 
    void SetSize(const size_t n)
    {
        Matr.resize(n);
        for(size_t i=0; i<n; ++i)
            Matr[i].resize(n);
    }
 
    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<<"Введите вес V"<< i <<",V"<< j <<" дуги\n"
                        <<"0 если вершины не соединены\n";
                    std::cin>>Matr[i][j];
                    if(Matr[i][j]==0)
                        Matr[i][j]=100;
                }
            }
        }
    }
protected:
    VM Matr;
};
 
class Floyd:public MatrixAdj
{
public:
    Floyd():MatrixAdj()
    {
    }
 
    ~Floyd()
    {
    }
 
    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();
    }
    
    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;
                    }
                }
            }
        }
    }
 
    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);
        }
    }
 
    void PrintWMatr(std::ostream& os) const
    {
        PrintMatr(Matr, os);
    }
 
    void PrintSPMatr(std::ostream& os) const
    {
        PrintMatr(MatrSPath, os);
    }
 
    void PrintPMatr(std::ostream& os) const
    {
        PrintMatr(MatrPath, os);
    }
 
    void PrintSt(std::ostream& os)
    {
        while(!Path.empty())
        {
            os<<Path.top()<<' ';
            Path.pop();
        }
        os<<'\n';
    }
private:
    VM MatrPath;
    VM MatrSPath;
    ST Path;
    
    void PrintMatr(const VM& Vec, std::ostream& os) const
    {
        for(size_t i=0; i<Vec.size(); ++i)
        {
            for(size_t j=0; j<Vec.size(); ++j)
            {
                os<<std::setw(3)<<Vec[i][j]<<' ';
            }
            os<<'\n';
        }
    }
 
    void Copy()
    {
        MatrSPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrSPath[i].resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            std::copy(Matr[i].begin(), Matr[i].end(), MatrSPath[i].begin());
    }
};
 
std::ostream& operator <<(std::ostream& os, const Floyd& Ob)
{
    os<<"Матрица весов\n";
    Ob.PrintWMatr(os);
    os<<"Матрица путей\n";
    Ob.PrintSPMatr(os);
    os<<"Матрица кратчайших путей\n";
    Ob.PrintPMatr(os);
    int letter = cin.get();
    return os;
    
}
 
#endif

Floyd.cpp
Кликните здесь для просмотра всего текста
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
#include "stdafx.h"
#include <iostream>
#include <windows.h>
#include <algorithm> 
#include "Floyd.h"
using namespace std;
using namespace System;
 
int main()
{
    try
    {
        setlocale( LC_ALL, "russian");
        int n;
        std::cout<<"Введите количество вершин: ";
        std::cin>>n;
        Floyd Ob;
        Ob.SetSize(n);
        Ob.Fill();
        Ob.Initialise();
        Ob.FindPathMatr();
        std::cout<<Ob;
        size_t first, second;
        std::cout<<"ВВедите начальную и конечную вершину для поиска между ними кратчайшего пути:\n";
        std::cin>>first>>second;
        Ob.FindPath(first, second);
        std::cout<<"Кратчайший путь между " << first <<" и "<< second <<" вершиной:\n";
        Ob.PrintSt(std::cout);
        int letter = cin.get();
    }
    catch(std::exception& e)
    {
        std::cerr<<e.what()<<'\n';
        return 1;
    }
    int letter = cin.get();
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru