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

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

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

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

25.03.2014, 14:50. Просмотров 241. Ответов 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");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.03.2014, 14:50     Матрица путей в алгоритме Флойда-Уоршела
Посмотрите здесь:

Не могу найти ошибку в алгоритме Флойда-Уоршелла - 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++
Помогите написать программу на С++!!! (Console Application) Очень срочно надо!!!

Алгоритм Флойда-Уоршалла граф - C++
Собственно мне дан ориентированный граф,в котором вес ребра между вершинами i и j допустим-это шанс добраться от вершины i к вершине j...

В чем ошибка? Алгоритм Флойда - C++
Не понимаю почему не запускается, может нужна еще кака-набудь библиотека? Программу нашел в интернете #include &lt;vcl.h&gt; #pragma...

Нахождение кратчайшего расстояния методом Флойда - C++
Программа спрашивает кол-во вершин . И должно последовательно вводится расстояние между всеми вершинами. НО вводится лишь расстояние...

Ошибка в алгоритме - C++
Неправильно работает программа есть сетка (координаты x - в векторе A y - в векторе B) надо из известных точек проложить кратчайший...

Ошибка в алгоритме - C++
Помогите найти ошибку в алгоритме. Алгоритм должен сортировать строки. void SortArrayString(string *&amp;arr, int n, char arr2) /* arr...

Ошибка в алгоритме Дейкстры - C++
Помогите, пожалуйста исправить ошибки в коде! Не объявлены идентификаторы &quot;all&quot; &quot;information&quot; &quot;output&quot;, в некоторых местах отсутствуют &quot;;&quot;....


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

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

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