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

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

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

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

28.06.2011, 22:40. Просмотров 952. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос "Поиск путей на графах". С++ (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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 Посмотреть сообщение
код работает
ну и хорошо)))
xeops
0 / 0 / 0
Регистрация: 21.06.2011
Сообщений: 34
28.06.2011, 23:57  [ТС] #15
мне бы просто зацикливание из первой работы убрать....она как бы тоже пригодится...я вот не понимаю почему она выводит х0 постоянно
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2011, 23:57
Привет! Вот еще темы с ответами:

Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" - C++
Функция - расчёт зарплаты по нагрузке и оплате часа для определенной категории. Категория Оплата часа Вторая 150 Первая 200 ...

Создать иерархию классов "Фирма", "Бухгалтер", "Сотрудник", "Зарплата" - C++
Само по себе понятие &quot;зарплата&quot; не особенно конкретное: оно включает и почасовую, и ставочную зарплату, и комиссионные, и процент с продаж....

по строкам.замените в слове сочетание "му" на "а" , а букву "ы" на "ца". очень нужно - C++
замените в слове сочетание &quot;му&quot; на &quot;а&quot; , а букву &quot;ы&quot; на &quot;ца&quot;. очень нужно Добавлено через 21 час 4 минуты неужели никто не знает...

Реализовать структуру "Анкета" с полями "Фамилия", "Пол" и "Адрес" - C++
Здравствуйте. Проходим тему Структуры, не могу понять, как определить количество, само задание: #include &lt;iostream&gt; #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.06.2011, 23:57
Ответ Создать тему
Опции темы

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