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

Матрица путей в алгоритме Флойда-Уоршела - C++

Восстановить пароль Регистрация
 
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
25.03.2014, 14:50     Матрица путей в алгоритме Флойда-Уоршела #1
Добрый день, подскажите пожалуйста, в чем ошибка?

Написал программу, которая считает наименьший путь между всеми парами вершин в графе, используя алгоритм Флойда-Уоршела.

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
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;
 
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
 
for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
}
}
//главная функция
int main(void)
{
setlocale(LC_ALL, "En");
cout<<"Kol-vo vershin v grafe > "; cin>>n;
cout<<"Vvedite matricy vesov reber:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<"Matrica kratchaishih putey:"<<endl;
FU(GR, n);
cout<<"Tablica putey:"<<endl;
 
system("pause>>void");
}
В ответе получается матрица, в которой содержатся все наименьшие по весу соединения между вершинами.

Теперь пытаюсь сделать так, чтобы создавалась еще одна матрица, в которой будут отображаться пути, по которым получились наименьшие веса.
Пример: матрица p[i][j] заполняется коэфициентами i j
0 12 13
21 0 23
31 32 0

Матрица должна прийти к такому виду:

0 132 13
21 0 213
31 32 0

То есть, мы видим, что после преобразований короткий путь будет проходить через (например, второй элемент в первом столбце будет проходить через 3 ребро, а не напрямую)

Вот код:

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
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
int PR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;
 
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
 
for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
}
}
void PU(int P[][maxV], int V)
{
int k;
for (i=0; i<V; i++) P[i][i]=0;
 
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (P[i][k] && P[k][j] && i!=j)
if (P[i][k]+P[k][j]<P[i][j] || P[i][j]==0)
P[i][j]=i;
 
for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<P[i][j]<<"\t";
cout<<endl;
}
}
//главная функция
int main(void)
{
setlocale(LC_ALL, "En");
cout<<"Kol-vo vershin v grafe > "; cin>>n;
cout<<"Vvedite matricy vesov reber:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<"Matrica kratchaishih putey:"<<endl;
FU(GR, n);
cout<<"Tablica putey:"<<endl;
PU(PR, n);
system("pause>>void");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.03.2014, 14:50     Матрица путей в алгоритме Флойда-Уоршела
Посмотрите здесь:

C++ Сортировка всплытием Флойда
C++ алгоритм Флойда-Уоршелла
C++ Алгоритм Флойда–Уоршелла
двумерная матрица путей городов C++
C++ Алгоритм Флойда Оршала
Алгоритм Флойда-Уоршела C++
C++ ошибка у флойда
Не могу найти ошибку в алгоритме Флойда-Уоршелла C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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