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

Алгоритм Флойда - Уоршелла - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 128, средняя оценка - 4.61
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 18:07     Алгоритм Флойда - Уоршелла #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
43
44
#include "stdafx.h"
#include "iostream"
#include "string.h"
#include "conio.h"
#include "stdlib.h"
#include "stdio.h"
 int d[4][4];
using namespace std;
 
int main()
{
 
    FILE *p, *v;
    int i, j, m, k;
    const int n=4;
// ввод исходных данных
    p=fopen("vxod.txt", "r");
    if(p == 0)
    {
        printf("Невозможно открыть данный файл 's'", "vxod.txt");
        return 0;
    };
    while ((m=getc(p))!=EOF)
        putchar(m);
// ввод исходных данных закончен
 
for (int k=0; k<n; ++k)
{
    for (int i=0; i<n; ++i)
    {
            for (int j=0; j<n; ++j)
            {
            d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
            cout << d[i][j];
            }
        
    }
}
    fclose (p);
system ("\n pause");
exit(0);
_getch();
    return 0;
}
вот текст файла
4
1 0 2 3 4
2 1 0 4 3
3 1 2 0 2
4 4 3 1 0

Алгоритм Флойда-Уоршелла нахождения кратчайших путей между всеми парами вершин.

мне надо найти вершину, чтоб между нею и другими вершинами., не более 4
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.12.2010, 18:07     Алгоритм Флойда - Уоршелла
Посмотрите здесь:

C++ Алгоритм Флойда (теория графов)
Алгоритм Флойда-Уоршелла (результат работы неправильный) C++
C++ Алгоритм Флойда–Уоршелла
C++ Алгоритм Флойда Оршала
Алгоритм Флойда-Уоршела C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.12.2010, 18:20     Алгоритм Флойда - Уоршелла #2
Дискретная математика
Тут ж есть алгоритм.
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 19:03  [ТС]     Алгоритм Флойда - Уоршелла #3
а каким образом там массив вводится?: я чего то не поняла

Добавлено через 5 минут
я там похоже даже в вводе данных запуталась

Добавлено через 18 минут
вроде чуть разобралась там несколько алгоритмов, а который из них Флойда-Уоршелла, точнее что там к нему относится???

Добавлено через 6 минут
Как я поняла вот эти части кода относятся к тому чтоо мне надо, ? следавотельно к чему относится остальное, и надо ли оно мне? и что я упстила?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 void FindPathMatr()
        {
                for(size_t k=0; k<Matr.size(); ++k)
                {
                        for(size_t i=0; i<Matr.size(); ++i)
                        {
                                for(size_t j=0; j<Matr.size(); ++j)
                                {
                                        int b=MatrSPath[i][k]+MatrSPath[k][j];
                                        if(b<MatrSPath[i][j])
                                        {
                                                MatrSPath[i][j]=b;
                                                MatrPath[i][j]=k;
                                        }
                                }
                        }
                }
        }
C++
1
 Ob.FindPathMatr();
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.12.2010, 19:23     Алгоритм Флойда - Уоршелла #4
White Luna, Там вся программа алгоритм Флойда Уоршалла...

Добавлено через 8 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
       void Fill()
        {
                for(size_t i=0; i<Matr.size(); ++i)
                {
                        for(size_t j=0; j<Matr.size(); ++j)
                        {
                                if(i==j)
                                        Matr[i][j]=0;
                                else if(i>j)
                                {
                                        Matr[i][j]=Matr[j][i];
                                }
                                else
                                {
                                        std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                                                <<"0 for not connect them\n";
                                        std::cin>>Matr[i][j];
                                        if(Matr[i][j]==0)
                                                Matr[i][j]=100;
                                }
                        }
                }
        }
Это заполнение матрицы смежности.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        void Initialise()
        {
                MatrPath.resize(Matr.size());
                for(size_t i=0; i<Matr.size(); ++i)
                        MatrPath[i].resize(Matr.size());
                for(size_t i=0; i<MatrPath.size(); ++i)
                {
                        for(size_t j=0; j<MatrPath.size(); ++j)
                        {
                                if(Matr[i][j]==100)
                                        MatrPath[i][j]=100;
                                else
                                        MatrPath[i][j]=j;
                        }
                }
                Copy();
        }
Это создание матрицы путей.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
        void FindPathMatr()
        {
                for(size_t k=0; k<Matr.size(); ++k)
                {
                        for(size_t i=0; i<Matr.size(); ++i)
                        {
                                for(size_t j=0; j<Matr.size(); ++j)
                                {
                                        int b=MatrSPath[i][k]+MatrSPath[k][j];
                                        if(b<MatrSPath[i][j])
                                        {
                                                MatrSPath[i][j]=b;
                                                MatrPath[i][j]=k;
                                        }
                                }
                        }
                }
        }
Инициализация матрицы кратчайших путей нужными значениями.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
        void FindPath(size_t first, size_t second)
        {
                if(first>=MatrPath.size() || second>=MatrPath.size())
                        throw std::invalid_argument("One of nodes for searching is more than Matr size");
                ST Goals;
                Path.push(first);
                Goals.push(second);
                while(!Goals.empty())
                {
                        int u=Path.top();
                        int v=Goals.top();
                        int s=MatrPath[u][v];
                        if(v==s)
                        {
                                Path.push(v);
                                Goals.pop();
                        }
                        else
                                Goals.push(s);
                }
        }
Это нахождение пути от вершины к другой вершине. Вершины вводятся из main-а с клавиатуры. Через два стека. Не самый оптимальный алгоритм. У меня есть оптимальнее на бумаге, но переделывать пока лень.
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 19:28  [ТС]     Алгоритм Флойда - Уоршелла #5
тогда можешь пояснить каким образом там идет ввод данных

Добавлено через 3 минуты
блин.... тогда по идеи мне первые 2 пункта которые ты выделил не нужны т к я матрицу смежности ввожу как файл, так меньше мороки, и более понятно, но потом у ми возникают проблемы как её определить
BrumbleHorse
 Аватар для BrumbleHorse
120 / 120 / 11
Регистрация: 18.09.2010
Сообщений: 212
13.12.2010, 19:35     Алгоритм Флойда - Уоршелла #6
Этот алгоритм на с++ есть здесь
http://khpi-iip.mipk.kharkiv.edu/lib.../din_0100.html
все нормально работает..
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.12.2010, 19:54     Алгоритм Флойда - Уоршелла #7
BrumbleHorse, Это не тот алгоритм. Это алгоритм Уоршалла (по ссылке), а не Флойда-Уоршалла

Добавлено через 35 секунд
White Luna, То есть матрица путей у тебя тоже прям из файла береться? оО
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 22:45  [ТС]     Алгоритм Флойда - Уоршелла #8
ForEveR, у меня там тока одна матрица
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.12.2010, 23:26     Алгоритм Флойда - Уоршелла #9
White Luna, Ну да. А матрицу путей формировать? Вообще посмотри в инете четкий алгоритм. Я делал по алгоритму который давали на лекции.
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
13.12.2010, 23:40  [ТС]     Алгоритм Флойда - Уоршелла #10
нашла тут один код реализации, только не понимаю его вывод кто нить может пояснить каким образом там так считается
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
#include <iostream.h>
#define MaxNodes 4
#define B 1000
 
class Warshall
{
  private:
    unsigned Adj[MaxNodes][MaxNodes]; //Матрица смежностей.
    unsigned C[MaxNodes][MaxNodes];   //Матрица достижимости.
  public:
    void Vvod();
    void MinDlin();
    void Vyvod();
};
 
void Warshall::Vvod()
//Ввод матрицы смежностей заданного графа и ее "исправление".
{
  //Ввод матрицы смежностей заданного графа.
  cout <<"Вводите элементы матрицы смежностей по строкам:\n";
  for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
     {
       cout <<"Введите Adj["<< (i+1) << "]["<< (j+1) << "]: ";
       cin >> Adj[i][j];
       if (Adj[i][j]==0) C[i][j] = B;
       else  C[i][j] = Adj[i][j];
     }
}
 
void Warshall::MinDlin()
//Вычисление матрицы минимальных длин путей.
{
  for (int k=0;k<MaxNodes;k++)
   for (int i=0;i<MaxNodes;i++)
    for (int j=0;j<MaxNodes;j++)
       if ( C[i][j]>C[i][k]+C[k][j] ) 
              C[i][j] = C[i][k]+C[k][j];
}
 
void Warshall::Vyvod()
//Вывод матрицы минимальных длин путей.
{
  cout << "Матрица минимальных длин путей:\n";
  for (int i=0;i<MaxNodes;i++)
  {
    for (int j=0;j<MaxNodes;j++)
      cout << C[i][j] << " ";
    cout << endl;
  }
}
 
void main()
{
  Warshall A;
  A.Vvod();
  A.MinDlin();
  A.Vyvod();
}
Добавлено через 6 минут
Из-за чего получается такая матр нижняя
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Вводите элементы матрицы смежностей по строкам:
Введите Adj[1][1]: 0
Введите Adj[1][2]: 1
Введите Adj[1][3]: 2
Введите Adj[1][4]: 2
Введите Adj[2][1]: 6
Введите Adj[2][2]: 0
Введите Adj[2][3]: 4
Введите Adj[2][4]: 3
Введите Adj[3][1]: 2
Введите Adj[3][2]: 6
Введите Adj[3][3]: 0
Введите Adj[3][4]: 6
Введите Adj[4][1]: 9
Введите Adj[4][2]: 6
Введите Adj[4][3]: 6
Введите Adj[4][4]: 0
Матрица минимальных длин путей:
4 1 2 2
6 7 4 3
2 3 4 4
8 6 6 9
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.12.2010, 23:43     Алгоритм Флойда - Уоршелла #11
White Luna, Матрица минимальных путей. Нарисуйте граф на бумаге и проверьте
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
14.12.2010, 00:25  [ТС]     Алгоритм Флойда - Уоршелла #12
как минимальные пути матрицы считаются?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
14.12.2010, 00:41     Алгоритм Флойда - Уоршелла #13
White Luna, по алгоритму. А если вручную и граф маленький в уме.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.12.2010, 00:57     Алгоритм Флойда - Уоршелла
Еще ссылки по теме:

Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла C++
Не могу найти ошибку в алгоритме Флойда-Уоршелла C++
C++ Алгоритм Флойда-Уоршалла граф

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

Или воспользуйтесь поиском по форуму:
White Luna
 Аватар для White Luna
32 / 26 / 2
Регистрация: 08.09.2010
Сообщений: 402
14.12.2010, 00:57  [ТС]     Алгоритм Флойда - Уоршелла #14
я поняла это просто мы графы не проходили, и понимаю норм тока как матрицы строятся
Yandex
Объявления
14.12.2010, 00:57     Алгоритм Флойда - Уоршелла
Ответ Создать тему
Опции темы

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