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

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

Войти
Регистрация
Восстановить пароль
 
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
#1

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

25.03.2014, 14:50. Просмотров 243. Ответов 0
Метки нет (Все метки)

Добрый день, подскажите пожалуйста, в чем ошибка?

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

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");
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.03.2014, 14:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Матрица путей в алгоритме Флойда-Уоршела (C++):

Алгоритм Флойда-Уоршела - C++
Ребят, помогите. На завтра нужно сдать алгоритм флойда. Вроде нашел код, но он не выводит САМО ЗНАЧЕНИЕ кратчайшего пути, а только по каким...

Не могу найти ошибку в алгоритме Флойда-Уоршелла - C++
Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины s в...

Двумерная матрица путей городов - C++
Здравствуйте! Есть 9 городов. Kyzylorda, Atyrau, Almaty, Astana, Kostanai, Pavlodar, Semipalatinsk, Ust-Kamenagorsk, Uralsk....

ошибка у флойда - C++
помогите найти ошибку: #include &lt;fstream&gt; #include &lt;iostream&gt; #include &lt;windows.h&gt; #include &lt;wincon.h&gt; using namespace std; ...

Алгоритм Флойда–Уоршелла - C++
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++) как сделать так, чтобы алгоритм нахождения кратчайшего...

Алгоритм Флойда - Уоршелла - C++
не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули или вообще ничего, ошибок не выводит не...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.03.2014, 14:50
Привет! Вот еще темы с ответами:

Сортировка всплытием Флойда - C++
Помогите написать программу на С++!!! (Console Application) Очень срочно надо!!!

Алгоритм Флойда Оршала - C++
Найти наикратчайшее расстояние от каждой до каждой. Задание представляет собой любую матрицу 4*4. Программа на языке C++.

Алгоритм Флойда С++ реализация - C++
Есть такой код класса Помогите, пожалуйста найти по методу Флойда самый короткий путь, он описан в void setstructGraf, но не могу...

дана квадратичная матрица z[n][n]. составить программу, которая если матрица симметричная(транспонированная матрица равна исходной), сделает ее не сим - C++
помогите пожалуйста. условие: дана квадратичная матрица z. составить программу, которая если матрица симметричная(транспонированная...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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