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

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

Войти
Регистрация
Восстановить пароль
 
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
#1

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

28.06.2011, 22:40. Просмотров 948. Ответов 14
Метки нет (Все метки)

Задача.
Для некоторого ориентированного графа задана матрица весов 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 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.06.2011, 22:40     "Поиск путей на графах". С++
Посмотрите здесь:

Реализовать поиск в массиве структур "Znak" по заданному полю - C++
Описать структуру с именем znak, содержащую следующие поля: • фамилия, имя; • знак Зодиака; • дата рождения (массив из трех чисел). ...

Реализовать поиск в массиве структур "Student" по заданному полю - C++
Я очень мало понимаю в программировании, но лабораторные как-то надо сдавать, учитывая, что препод ничего не объясняет(( Ребят, помогите...

Бинарный поиск, ошибка: "Invalid operands to binary expression" - C++
При компиляции программы XCode ругается на: algorithm:677:97: Invalid operands to binary expression ('const Luggage' and 'int') Сломал...

Бинарное дерево поиска: "Библиотека", поиск по автору книги - C++
Есть бинарное дерево поиска.Дерево представляет собой подобие библиотеки.Нужно осуществить поиск по фамилии автора книги.Для ситуации один...

Поиск чисел, "простых для заданного набора" - C++
Условие задачи: Дан набор различных натуральных чисел. Будем называть число &quot;простым для заданного набора&quot;, если число не делится ни на...

Поиск значения в памяти приложения ("Нет" читам!) - C++
Здравствуйте, жители КиберФорума! Играл недавно в немало известную игру Sniper Elite(1 часть, мультиплеер), читеров оказалось хоть ж*п*й...

Реализовать поиск по заданному полю в массиве объектов типа "Абитуриент" - C++
При поступлении в университет лица, получившие оценку «неудовлетворительно» на первом экзамене, ко второму экзамену не допускаются. Считая...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 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++
4669 / 2495 / 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++
4669 / 2495 / 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++
4669 / 2495 / 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++
4669 / 2495 / 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++
4669 / 2495 / 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++
4669 / 2495 / 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++
Здравствуйте, нужна помощь, нужно доработать код, но не совсем понимаю как Вот код (что именно нужно доработать ниже) #include...

Реализовать поиск по заданному полю в массиве объектов типа "Bus" - C++
. Bus: Фамилия и инициалы водителя, Номер автобуса, Номер маршрута, Марка, Год начала эксплуатации, Пробег. Создать массив объектов....

Реализовать поиск по заданному полю в массиве объектов типа "Знак зодиака" - C++
Помогите закончить программу. Это я еще буду переделывать, потому что есть недостатки. нужно: *1) Удалить все данные о человеке, фамилия...

Поиск дискриминанта, АТД "Квадратное уравнение" - C++
нужно создать АТД квадратное уравнение, с выводом корней и самого уравнения на экран. Вывод уравнения, вроде, проходит нормально, а вот...

Поиск файлов c расширением ".jpg" в папке - C++
Добрый день! Подскажите как лучше реализовать поиск в папке файлов з расширениям .jpg? Как бы есть программа для роботы з изображениями...


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

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

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