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

"Поиск путей на графах". С++ - C++

Восстановить пароль Регистрация
 
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 22:40     "Поиск путей на графах". С++ #1
Задача.
Для некоторого ориентированного графа задана матрица весов W. С помощью алгоритма Форда-Беллмана вычислить веса кратчайших путей, исходящих из первой вершины, до остальных вершин.
Помогите плиз) Задача родом из дискретной математики....
вот примерный код..но он зациклен почему то в конце...

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
// 1.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <sstream>
 
using namespace std;
 
const int N = 100; 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
 
    setlocale (LC_ALL,"Russian");
    
    int a[N][N];
    int c[N][N];
    
    
    int n, i, j, i1,j1;
    
    int kolvo = 0;
    int kolvo1 = 0;
    int b, b1, h1, u1, h, u,k;
    b = 0;
    b1 = 0;
    u = 0;
    u1 = 0;
    h = 0;
    h1 = 0;
 
 
    cout << "введите количество вершин в графе: ";
    cin >> n;
 
    cout <<endl << "введите матрицу весов";
    cout << endl;
 
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            cin>> a[i][j];
            a[i][j];
            
            cout << "     ";
        }
        cout << endl;
    }
 
    cout << "Введите конечную вершину: ";
    cin >> k;
    cout << endl;
    
    for (i = 0; i < n+1; i++)
    {
        c[i][0] = 100;
    }
 
    for (j = 0; j < n+1; j++)
    {
        c[0][j] = 100;
    }
 
    c[0][1]= 0;
    c[1][0]=0;
 
    
    i1 = 0;
 
    for (i = 1; i < n+1; i++)
    {
        j1 = 0;
 
        for (j = 1; j < n+1;j++)
        {
            c[i][j] = a[i1][j1];
            j1++;
        }
        i1++;
    }
    for (i = 0; i < n+1; i++)
    {
        for (j = 0; j < n+1;j++)
        {
            cout << c[i][j] << "    ";
            
        }
        cout << endl;
    }
 
    for (i = 1; i < n+1; i++)
    {
        for (j = 1; j < n+1; j++)
        {
            if (c[i][j] != 1000)
            {
                if (c[0][j] == 100)
                {
                    c[0][j] = c[i][j] + c[i][0];
                    c[j][0] = c[0][j];
                }
            }
        }
    }
 
    cout << endl;
for (i = 0; i < n+1; i++)
    {
        for (j = 0; j < n+1;j++)
        {
            cout << c[i][j] << "    ";
            
        }
        cout << endl;
    }
 
    for (i = 1; i < n+1; i++)
    {
        for (j = 1; j < n+1; j++)
        {
            if ((c[i][j] + c[i][0]) < c[0][j])
            {
                c[0][j] = (c[i][j] + c[0][i]);
                c[j][0]= c[0][j];
            }
        }
    }
    cout << endl;
for (i = 0; i < n+1; i++)
    {
        for (j = 0; j < n+1;j++)
        {
            cout << c[i][j] << "    ";
            
        }
        cout << endl;
    }
 
    cout << "длина кратчайшего пути равна: ";
    cout << c[0][k+1];
    cout << endl;
 
    h = k+1;
 
    cout << "х" << k << " ";
 
    
    
    for (i = 1; i < n+1; i++)
    {
        if (c[i][h]+c[i][0] == c[0][h])
        {
            cout <<"х" << i-1 << " ";
            h = i;
            i = 0;
        }
    }
    
 
    
 
    getch();
    return 0;
}
 Комментарий модератора 
Используйте теги форматирования кода!
Вложения
Тип файла: doc Лаб 05 - Поиск путей на графах.doc (41.0 Кб, 35 просмотров)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:04     "Поиск путей на графах". С++ #2
Саму реализацию алгоритма не проверял. Но вот в этом моменте может быть и зацикливание. Точно нужно внутри этого цикла менять значение i ?
Цитата Сообщение от xeops Посмотреть сообщение
for (i = 1; i < n+1; i++)
{
if (c[i][h]+c[i][0] == c[0][h])
{
cout <<"х" << i-1 << " ";
h = i;
i = 0;
}
}
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:07  [ТС]     "Поиск путей на графах". С++ #3
да я как бы не знаю...алгоритм у меня если честно вызывает сомнения...так что конец кода я вообще не пойму
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:11     "Поиск путей на графах". С++ #4
xeops, А сам код откуда брали?
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:13  [ТС]     "Поиск путей на графах". С++ #5
сам код мы с одногруппником писали...но я писал верхнюю часть...он заканчивал..но что то он натворил...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:17     "Поиск путей на графах". С++ #6
Цитата Сообщение от xeops Посмотреть сообщение
но я писал верхнюю часть...
А Вы написали все верно?:
Цитата Сообщение от xeops Посмотреть сообщение
cout <<endl << "введите матрицу весов";
cout << endl;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
cin>> a[i][j];
a[i][j];
cout << " ";
}
cout << endl;
}
Алгоритм откуда брали?
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:27  [ТС]     "Поиск путей на графах". С++ #7
принцип ввода таков,там есть приклепленное задание...в формате документа...но вместо бесконечности вводится 1000......вот и принцип...а алгоритм не помню..но рабочий..что то не так вышло с выводом в конце
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:37     "Поиск путей на графах". С++ #8
xeops, Проще найти на этом сайте рабочий вариант реализации алгоритма Форда-Беллмана или даже написать новый. А от задания Вы точно отклонились:
вычислить веса кратчайших путей, исходящих из первой вершины, до остальных вершин
А у Вас зачем-то:

Цитата Сообщение от xeops Посмотреть сообщение
cout << "длина кратчайшего пути равна: ";
cout << c[0][k+1];
cout << endl;
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:39  [ТС]     "Поиск путей на графах". С++ #9
ладно...я переделал лабу по другому пути реализации)))но все равно спасибо))
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:43     "Поиск путей на графах". С++ #10
Цитата Сообщение от xeops Посмотреть сообщение
но все равно спасибо))
не за что.

Цитата Сообщение от xeops Посмотреть сообщение
я переделал лабу по другому пути реализации
По какому другому пути если не секрет? Вроде в задании сказано только про алгоритм Форда-Беллмана
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:46  [ТС]     "Поиск путей на графах". С++ #11
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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
// findd graf.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <math.h>
#include <conio.h>
#include <iostream>
using namespace std;
 
void zapolnenie(double m[][100],int n);
 
int prov(int pk[], int d[], int n);
 
int prov(int pk[], int d[],int n)
{
    int s = 0;
 
    for(int i = 1; i<=n; i++)
 
        if(pk[i] != d[i])
 
            s++;
 
    if( s == 0)
 
        return 1;
 
    else
 
        return 0;
 
}
 
void zapolnenie(double m[][100],int n)
{
    for (int i = 1; i <= n; i++)
    {
        cout << " для вершины х"<<i<<": " ;
 
        for (int j = 1; j <= n; j++)
        {       
 
            cin >> m[i][j];
 
            if( m[i][j] == 0)
 
                m[i][j] = 100000;
        }
 
        cout << endl;
    }
 
 
 
 
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale (LC_ALL,"Russian");
 
    double m[100][100];
 
 
    int n;
 
    cout << "введите количество вершин графа: ";
 
    cin >> n;
 
    
    zapolnenie(m,n);
 
    
    
    int s;
 
    cout << "введите начальную вершину "<<endl;
 
    cin >> s; int  v1er = s;
 
    int ss;
 
    cout << "введите конечную вершину "<<endl;
 
    cin >> ss;
 
    int mm;
 
    int min;
 
    int d[100];
 
    int pk[100];
 
    d[s]= 0;
 
 
    int v[100];
 
    int k =0;
 
    v[k] = s;
 
    k++;
 
 
 
 
    for(int i = 1; i<=n; i++)
    {
        if(d[i] != d[s])
 
            d[i] = 1000;
    }
 
 
 
 
 
    for(int i = 1; i <=n; i++)
 
        if(d[i] != d[s])
        {
            min = d[i];
 
            break;      
        }
 
 
    
    do {
 
 
    for(int i = 1; i<=n; i++)
 
        pk[i] = d[i];
 
 
 
 
 
    for(int i = 1; i <=n; i++)
 
        if(i != s)
        {
            if(d[i] > d[s] + m[s][i])
            {
                min = d[s] + (int)m[s][i];
 
                d[i] = min;
            }
 
        }
 
 
    int prom = 0;
 
    for(int i = 1; i <= n; i++)
    {
        if(i != s)
        {
            for(int j = 0; j <k; j++)
            {
                if(v[j] == i)
 
                    prom ++;
            }
 
            if (prom == 0)
            {
                min = d[i];
 
                break;
            }
 
            prom = 0;
            
            
            }
 
        
 
                
        
        }
 
 
    prom = 0;    
 
    for(int i = 1; i <= n; i++)
 
        if( i != s)
        {
            for(int j = 0; j <k; j++)
            {
                if(v[j] == i)
 
                    prom ++;
            }
 
            if( prom == 0)
            {
                    if( min >= d[i])
                    {
                        min = d[i];
 
                        s = i;
 
                        prom = 0;
                    }
 
            }
 
            prom = 0;
        
        }
 
    
 
 
    v[k] = s;
 
    k++;
 
     mm = prov(pk, d, n);
 
    }
 
    while( mm != 1 );
 
    cout << "из вершины "<< v1er <<" в вершину "<< ss <<" через вершины :"; 
 
    for(int i = 0; i < k - 1; i++)
 
        cout << " --> "<< v[i];
 
    cout << endl << " кратчайший путь = "<<d[ss];
 
 
 
    getch();
 
    return 0;
}
 Комментарий модератора 
Используйте теги форматирования кода!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:51     "Поиск путей на графах". С++ #12
Работает этот код?
А то что-то у меня сомнения:

Цитата Сообщение от xeops Посмотреть сообщение
while( mm != 1 );
Тоже друг заканчивал программу?
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:52  [ТС]     "Поиск путей на графах". С++ #13
нет,и да,код работает
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.06.2011, 23:55     "Поиск путей на графах". С++ #14
Цитата Сообщение от xeops Посмотреть сообщение
код работает
ну и хорошо)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2011, 23:57     "Поиск путей на графах". С++
Еще ссылки по теме:

C++ Структура "Автобус". Организовать поиск по номеру маршрута
Бинарный поиск, ошибка: "Invalid operands to binary expression" C++
C++ Поиск файлов c расширением ".jpg" в папке

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

Или воспользуйтесь поиском по форуму:
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:57  [ТС]     "Поиск путей на графах". С++ #15
мне бы просто зацикливание из первой работы убрать....она как бы тоже пригодится...я вот не понимаю почему она выводит х0 постоянно
Yandex
Объявления
28.06.2011, 23:57     "Поиск путей на графах". С++
Ответ Создать тему
Опции темы

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