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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Исправьте пожалуйста код http://www.cyberforum.ru/cpp-beginners/thread1129272.html
Есть код , как сделать чтобы числа a,b,c вводились с клавиатуры... (Программа находит булеан чисел a,b,c) Код программы: #include<iostream> void Print(char *a, int n, int i) { if (n) { if (n & 1)
C++ Исправить ошибку с выводом (оператор if else) С клавиатуры вводятся числа A B C D нужно определить упорядочены ли они по убыванию вострастанию или неупорядочены: #include <iostream> using namespace std; int main() { int A,B,C,D; cout<<"Enter A,B,C,D:"; cin>>A>>B>>C>>D; if(A<=B && B<=C && C<=D) http://www.cyberforum.ru/cpp-beginners/thread1129258.html
C++ Написать модуль, содержащий описание класса Дата
Написать модуль, содержащий описание следующего класса (использовать private и public) / C# Объект - дата этого года. Свойства - (Rw) день и месяц; - (Rw) день недели (при изменении выбирается ближайший день этого года); - (Ro) данный день - последний в месяце (boolean). Методы - конструктор, задает 1 января, - создать объект, представляющий день, симметричный данному дню в списке...
Где спряталась ошибка? C++
дана матрица. найти номер строки с отрицательным элементом. вводим значения и так далее все работает...но вот когда начинается сравнение каждого элемента с нулем то первую строку не обрабатывает, а если в начале строки стоял отрицательный элемент то и вовсе все элементы строки становятся равны значению первого элемента. корректно сравнит только во второй строке в ее середине.... в общем...
C++ Распарсить файл 3Dmax http://www.cyberforum.ru/cpp-beginners/thread1129226.html
Всем привет. В 3DMax есть возможность сохранять модели в формате obj это тоже самое что и txt. Вот пример элементарного объекта с текстурой. Возникло два вопроса. Первый.
C++ Структура - Окно c++ Структура - Окно. Структура должна включать соответствующие поля: размер окна, его положение на экране, цвет, текст в окне. Простейшие функции: отображение окна, удаление окна, изменение цветов, смена текста в окне. подробнее

Показать сообщение отдельно
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64

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

25.03.2014, 14:50. Просмотров 240. Ответов 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");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru